连绵的gin山百里长啊，微微耸起像屏障，压位~~~~——《压位之歌》

今天早上发现了一道耒阳新题，然后看到了好不容易卡掉了平衡树,然后线段树完虐……这句话于是学习了压位线段树。

然后发现跑的好慢啊囧。贴个代码就溜了：

/*
Date: 2014/09/02 10:41:20 Tuesday
Author: xllend3
*/
#include<cstdio>
#define rep(i,a,n) for(int _tmp=n,i=a;i<=_tmp;++i)
#define dep(i,a,n) for(int _tmp=n,i=a;i>=_tmp;--i)
using namespace std;
template<class T> inline void read(T&x){bool fu=0;char c;for(c=getchar();c<=32;c=getchar());if(c=='-')fu=1,c=getchar();for(x=0;c>32;c=getchar())x=x*10+c-'0';if(fu)x=-x;};
template<class T> inline void read(T&x,T&y){read(x);read(y);}
const int N=1111111,M=111111;
int l,m,n,t,C,opr;
typedef unsigned int u32;
u32 x,y;
u32 highze[65540],lowze[65540];
inline u32 high1(const u32 &x){
	if(x>>16)return highze[x>>16]+1;
	return highze[x&65535u]+17;
}
inline u32 low1(const u32 &x){
	if(x&65535u)return lowze[x&65535u]+1;
	return lowze[x>>16]+17;
}
struct BITSET{
	u32 a[N];
	inline void set(const int &w) {
		a[w>>5]|=1u<<(w&31);
	}
	inline void set0(const int &w) {
		a[w>>5]&=~(1u<<(w&31));
	}
	inline int get(const int &w) {
		return a[w>>5]&(1u<<(w&31));
	}
}bs[5];
int main()
{
    freopen("3685.in","r",stdin);freopen("3685.out","w",stdout);
    read(n,C);
    highze[0]=16;lowze[0]=0;
    rep(i,1,65535){
    	highze[i]=highze[i>>1]-1;
    	if(i&1)lowze[i]=0;else lowze[i]=lowze[i>>1]+1;
	}
	int dep=4,pt=1;
    rep(_,1,C){
    	read(opr);
			switch(opr){
    		case 1:
    			read(x);if(!bs[0].get(x))rep(i,0,4){
    				bs[i].set(x);x=x>>5;
				}
    			break;
    		case 2:
    			read(x);if(bs[0].get(x)){
    				bs[0].set0(x);
    				rep(i,1,4){
    					x=x>>5;
    					if(bs[i-1].a[x])bs[i].set(x);
    					else bs[i].set0(x);
					}
				}
    			break;
    		case 3:
    			if(!bs[4].a[0]){puts("-1");continue;}
    			dep=4;pt=0;
    			while(dep>=0){
    				pt=low1(bs[dep].a[pt])-1+(pt<<5);
    				dep--;
				}printf("%d\n",pt);
    			break;
    		case 4:
    			if(!bs[4].a[0]){puts("-1");continue;}
    			dep=4;pt=0;
    			while(dep>=0){
    				pt=32-high1(bs[dep].a[pt])+(pt<<5);
    				dep--;
				}printf("%d\n",pt);
    			break;
    		case 5:
    			read(x);dep=0;
    			while(dep<5){
    				if(bs[dep].a[x>>5]&(1u<<(x&31))-1)break;
    				dep++;x>>=5;
				}if(dep==5){puts("-1");continue;}
				pt=32-high1(bs[dep].a[x>>5]&(1u<<(x&31))-1)+(x&~31u);
				dep--;
    			while(dep>=0){
    				pt=32-high1(bs[dep].a[pt])+(pt<<5);
    				dep--;
				}printf("%d\n",pt);
    			break;
    		case 6:
    			read(x);dep=0;
    			while(dep<5){
    				if(bs[dep].a[x>>5]&~(~0u>>(31&~x)))break;
    				dep++;x>>=5;
				}if(dep==5){puts("-1");continue;}
				pt=low1(bs[dep].a[x>>5]&~(~0u>>(31&~x)))-1+(x&~31u);
				dep--;
    			while(dep>=0){
    				pt=low1(bs[dep].a[pt])-1+(pt<<5);
    				dep--;
				}printf("%d\n",pt);
    			break;
    		case 7:
    			read(x);printf("%d\n",bs[0].get(x)?1:-1);
    			break;
		}
	}
    return 0;
}

UPD：已经用set水过。。。虽然没有std快。。。

UPD：经过一些鬼畜的常数优化终于刷到了rank12（我已经看不懂现在的代码了）

附现在的主程序：

switch(opr){
	case 1:
		read(x);if(!bs[0].get(x))rep(i,0,4){
			bs[i].set(x);x=x>>5;
		}
		break;
	case 2:
		read(x);if(bs[0].get(x)){
			bs[0].set0(x);
			rep(i,1,4){
				x=x>>5;
				if(bs[i-1].a[x])bs[i].set(x);
				else bs[i].set0(x);
			}
		}
		break;
	case 3:
		if(!bs[4].a[0]){pfu1;continue;}
		dep=4;pt=0;
		while(dep+1){
			pt=low1(bs[dep].a[pt])^(pt<<5);
			dep--;
		}putint(pt);
		break;
	case 4:
		if(!bs[4].a[0]){pfu1;continue;}
		dep=4;pt=0;
		while(dep+1){
			pt=(31&~high1(bs[dep].a[pt]))^(pt<<5);
			dep--;
		}putint(pt);
		break;
	case 5:
		read(x);dep=0;
		while(dep-5){
			if(bs[dep].a[x>>5]<<(31&~x)<<1)break;
			dep++;x>>=5;
		}if(dep==5){pfu1;continue;}
		pt=x-high1(bs[dep].a[x>>5]<<(31&~x)<<1)-1;
		dep--;
		while(dep+1){
			pt=(31&~high1(bs[dep].a[pt]))^(pt<<5);
			dep--;
		}putint(pt);
		break;
	case 6:
		read(x);dep=0;
		while(dep-5){
			if(bs[dep].a[x>>5]>>(x&31)>>1)break;
			dep++;x>>=5;
		}if(dep==5){pfu1;continue;}
		pt=low1(bs[dep].a[x>>5]>>(x&31)>>1)+1+x;
		dep--;
		while(dep+1){
			pt=low1(bs[dep].a[pt])^(pt<<5);
			dep--;
		}putint(pt);
		break;
	case 7:
		read(x);if(!bs[0].get(x))PC('-');
		PC('1');PC('\n');
		break;
}

• 相关文章
• 全局相关文章