2013-12-27

■ Bubble Sort (JOI 2013) 01:58

BITでO(N log N)で反転数求めてあとはそれなりの速さで

区間にひきたししたり最大値とったりすればいい。

というわけで遅延評価しましょう。

コード:

//Bokan ga bokka--nn!!
//Daily Lunch Special Tanoshii !!
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair P2;
typedef long long ll;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
//#define s(x) scanf("%d",&x)
#define rep(i,x) for(int i=0;i
#define s 131072
class segtree
{
public:
	ll seg[s*2];
	ll lazy[s*2];
	void init()
	{
		fill(seg,seg+s*2,-1000000000000000000LL);
		fill(lazy,lazy+s*2,-1000000000000000000LL);
	}
	void lazy_evaluate(int k)
	{
		if(k*2+2>=s*2) return ;
		lazy[k*2+2]+=lazy[k];
		lazy[k*2+1]+=lazy[k];
		seg[k*2+2]+=lazy[k];
		seg[k*2+1]+=lazy[k];
		lazy[k]=0;
	}
	ll update(int beg,int end,int idx,int lb,int ub,ll num)
	{
		if(beg>end) return -1000000000000000000LL;
		if(ubreturn seg[idx];
		}
		if(beg<=lb&&ub<=end)
		{
			lazy[idx]+=num;
			seg[idx]+=num;
			return seg[idx];
		}
		if(lazy[idx])
		{
			lazy_evaluate(idx);
		}
		return seg[idx]=max(update(beg,end,idx*2+1,lb,(lb+ub)/2,num),update(beg,end,idx*2+2,(lb+ub)/2+1,ub,num));
	}
	ll query(int beg,int end,int idx,int lb,int ub)
	{
		if(beg>end) return -1000000000000000000LL;
		if(ubreturn -1000000000000000000LL;
		}
		if(beg<=lb&&ub<=end)
		{
			return seg[idx];
		}
		if(lazy[idx])
		{
			lazy_evaluate(idx);
		}
		return max(query(beg,end,idx*2+1,lb,(lb+ub)/2),query(beg,end,idx*2+2,(lb+ub)/2+1,ub));
	}
}seg;
vector<int>vec;
int h[100005];
int bit[s+1];
void add(int i,int x)
{
	while(i<=s)
	{
		bit[i]+=x;
		i += (i & -i);
	}
}
int query(int i)
{
	int ret=0;
	while(i>0)
	{
		ret+=bit[i];
		i -= (i & -i);
	}
	return ret;
}
int score[100005];
P gray[100005];
bool used[100005]={};
bool eq[100005]={};
vector<int>check[100005];
bool one[100005]={};
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=0;i"%d",&h[i]);
		vec.pb(h[i]);
	}
	vec.pb(-INF);
	sort(vec.begin(),vec.end());
	vec.erase(unique(vec.begin(),vec.end()),vec.end());
	for(int i=0;i0ll;
	for(int i=0;i1);
	}
	if(ret==0) { cout<< ((vec.size()==n+1)?1:0) << endl; return 0;}
	vector<int>le,ley;
	vector<int>ri,riy;
	for(int i=0;iif(le.empty() || ley[le.size()-1]true;
		}
	}
	for(int i=n-1;i>=0;i--)
	{
		if(ri.empty() || riy[ri.size()-1]>h[i])
		{
			ri.pb(i);
			riy.pb(h[i]);
			used[i]=true;
		}
	}
	reverse(ri.begin(),ri.end());
	reverse(riy.begin(),riy.end());
	priority_queue,greater
 >notyet,already;
	for(int i=0;i1,-1);
		if(used[i]) continue;
		int ri=upper_bound(le.begin(),le.end(),i)-le.begin();
		ri--;
		int le=lower_bound(ley.begin(),ley.end(),h[i])-ley.begin();
		if(ley[le]==h[i])
		{
			eq[i]=true;
		}
		gray[i]=mp(le,ri);
		notyet.push(mp(i,h[i]));
		if(riy[lower_bound(riy.begin(),riy.end(),h[i])-riy.begin()]==h[i])
		{
			check[h[i]].pb(i);
			one[i]=true;
		}
	}
 
	ll res=0ll;
	//seg.init();
	for(int i=0;iwhile(!notyet.empty() && notyet.top().first<=ri[i])
		{
			if(!eq[notyet.top().first])
			{
				seg.update(gray[notyet.top().first].first,gray[notyet.top().first].second,0,0,s-1,2);
			}
			else
			{
				seg.update(gray[notyet.top().first].first,gray[notyet.top().first].first,0,0,s-1,1);
				seg.update(gray[notyet.top().first].first+1,gray[notyet.top().first].second,0,0,s-1,2);
			}
			already.push(mp(notyet.top().second,notyet.top().first));
			notyet.pop();
		}
		while(!already.empty() && already.top().firstint d=one[already.top().second];
			if(!eq[already.top().second])
			{
				seg.update(gray[already.top().second].first,gray[already.top().second].second,0,0,s-1,-2+d);
			}
			else
			{
				seg.update(gray[already.top().second].first+1,gray[already.top().second].second,0,0,s-1,-2+d);
				seg.update(gray[already.top().second].first,gray[already.top().second].first,0,0,s-1,-1+d);
			}
			already.pop();
		}
		for(int j=0;j0,0,s-1,-1);
		}
		res=max(res,seg.query(0,s-1,0,0,s-1)+1);
	}
	printf("%lld\n",ret-res);
}

こんなに長いの書いたの初めてです...(約4600B)

で、これをもって本選全部埋まりました...

明日からは春埋めます。(あとJMOの対策)

ツイートする