2014-01-02

■ IOI 2005 mountains 02:10

とりあえず思いついた解法:

座圧してサイズ200000以下にする。segtreeを組む。

で、"次のレールの傾きと今のレールの傾きが違う時"には高さをもっておき、その他は0にセットしておく。

(つまり最初は全部0)

で、傾き変更クエリは

座圧後のidxがx~yの範囲を傾きdに変更するとき xの高さ,xの高さ+(za[y]-za[x])*dでx,yを更新し、

x+1~y-1を0にする。

でy+1以降はある一定の値を足す。(今のy座標と昔のy座標の差)

ででき、

いけるかどうかは二分探索でやればよい。

実際これだと実装がつらかったのでkagamizさんの記事とhogloidさんのコードを参考にして解きました。

segtreeの構造を活かして解くとかわからない...

いつか最初の解法でやってみたい(KONMAI)

ツイートする

■ JOI Fortune telling 15:27

99%正しいコードからACまで2,3時間かかってしまいました(死)

箱根駅伝を見ながら実装するのはやめましょう。(戒め)

陥りやすいミス

・この問題で閉区間を使わないほうがいいです。

少数の人を除いて、座標圧縮をつかっていると思います。このとき閉区間の使用は控えましょう。

たとえば、通常時に[1~m][m+1~n]と分割しても万事okですが

座圧後のindexでこれをやるとindexがmの座標+1~indexがm+1の座標-1が抜け落ちることが

わかると思います。こんなときに半開区間が便利なんですね。理由はいうまでもないでしょう。

・遅延評価のsegtreeで、update()を再帰的に使う場合、

領域外でもその頂点の値をもどす。

範囲の値を求めているのではなく、"範囲の値を更新する"わけなので、

そこから外れてるからといって-1を返したりしてはいけないわけです。

この2つに気をつければそんなに難しくないような気はします

//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 (1<<18)
vectorquery;
vector<int>x;
class segtree
{
	public:
	int seg[s*2];
	int flag[s*2];
	void init()
	{
		memset(seg,0,sizeof(seg));
		memset(flag,0,sizeof(flag));
	}
	//座圧+閉区間、ダメ、ゼッタイ。
	//このsegtreeは半開区間ってそれ一番言われてるから
	//[x[a],x[b])ということってはっきりわかんだね
	//[x[l],x[r])
	void lazy_evaluate(int k,int l,int r)
	{
		if(flag[k]) seg[k]=x[r]-x[l]-seg[k];
		if(k1)
		{
			flag[k*2+1]^=flag[k];
			flag[k*2+2]^=flag[k];
		}
		flag[k]=false;
	}
	int update(int a,int b,int k,int l,int r)
	{
		lazy_evaluate(k,l,r);
		if(b<=l || r<=a) return seg[k];
		if(a<=l && r<=b)
		{
			flag[k]^=1;
			lazy_evaluate(k,l,r);
			return seg[k];
		}
		int le=update(a,b,k*2+1,l,(l+r)/2);
		int ri=update(a,b,k*2+2,(l+r)/2,r);
//cout << k << " " << le+ri << endl;
		return seg[k]=le+ri;
	}
	int query(int a,int b,int k,int l,int r)
	{
		return seg[0];
	}
}seg;
int main()
{
	int m,n;
	int k;
	scanf("%d %d %d",&m,&n,&k);
	for(int i=0;iint a,b,c,d;
		scanf("%d %d %d %d",&a,&b,&c,&d);
		query.pb(mp(c,mp(a,b+1)));
		query.pb(mp(d+1,mp(a,b+1)));
		x.pb(a); x.pb(b+1);
	}
	x.pb(0);
	while(x.size()!=s) x.pb(INF);
	sort(x.begin(),x.end()); sort(query.begin(),query.end());
	vector<int>ne; int prev=-1;
	for(int i=0;iif(prev!=x[i])
		{
			ne.pb(x[i]);
			prev=x[i];
		}
	}
	seg.init();
	x=ne;
	int xx=query[0].second.first; int yy=query[0].second.second;
	xx=lower_bound(x.begin(),x.end(),xx)-x.begin();
	yy=lower_bound(x.begin(),x.end(),yy)-x.begin();
	seg.update(xx,yy,0,0,s); // cout << xx  << " JJH " << yy << endl;
	ll ret=1LL*n*m;
	for(int i=1;i<=query.size();i++)
	{
		ret-=1LL*(seg.query(0,s,0,0,s))*((i==query.size()?m+1:query[i].first)-query[i-1].first);
//cout << (seg.query(0,s,0,0,s)) << " " << ((i==query.size()?m+1:query[i].first)-query[i-1].first) << endl;
		int l=lower_bound(x.begin(),x.end(),query[i].second.first)-x.begin();
		int r=lower_bound(x.begin(),x.end(),query[i].second.second)-x.begin();
		seg.update(l,r,0,0,s); //cout << l  << " JJH " << r << endl;
	}
	cout << ret << endl;
}

ツイートする