程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> ZOJ 3765 splay

ZOJ 3765 splay

編輯：C++入門知識

ZOJ 3765 splay

B - Lights Time Limit:8000MS Memory Limit:131072KB 64bit IO Format:%lld & %llu Submit Status

Description

Now you have N lights in a line. Don't worry - the lights don't have color. The only status they have is on and off. And, each light has a value, too.

There is a boring student in ZJU. He decides to do some boring operations to the lights:

Q L R status - Query the GCD (Greatest Common Divisor) of the value of the given status lights in range [L, R]. For example, if now we have 3 lights which are {on, off and on}, and their value are {3, 5, 9}, then the GCD of the number of the lights on in [1, 3] is 3, and the lights off is 5.I i value status - Add a light just behind to i^th light. The initial status and the value is given also.D i - Remove the i^th light.R i - If i^th light is on, turn it off, else turn it on.M i x - Modify the value of i^th light to x.

Please help this boring guy to do this boring thing so that he can have time to find a girlfriend!

Input

The input contains multiple test cases. Notice there's no empty line between each test case.

For each test case, the first line of the a case contains two integers, N (1 ≤ N ≤ 200000) and Q (1 ≤ Q ≤ 100000), indicating the number of the lights at first and the number of the operations. In following N lines, each line contains two integers, Num_i (1 ≤ Num_i ≤ 1000000000) and Status_i (0 ≤ Status_i ≤ 1), indicating the number of the light i and the status of it. In following Q lines, each line indicating an operation, and the format is described above.

It is guaranteed that the range of the operations will be appropriate. For example, if there is only 10 lights, you will not receive an operation like "Q 1 11 0" or "D 11".

Output

For each Query operation, output an integer, which is the answer to the query. If no lights are with such status, please output -1.

Sample Input

Sample Output

提取區間[L,R],Splay(L-1,0);Splay(R+1,root);[L,R]對應的區間為ch[ch[root][1]][0]，維護操作函數放到push_down和push_up裡就好。

/*************************************************************************
    > File Name: Spaly.cpp
    > Author: acvcla
    > QQ:
    > Mail: [email protected]
    > Created Time: 2014Äê11ÔÂ16ÈÕ ÐÇÆÚÈÕ 00Ê±14·Ö26Ãë
 ************************************************************************/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
const int maxn = 4e5 + 100;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
int ch[maxn][2],pre[maxn],key[maxn],gcd[maxn][2],siz[maxn],rev[maxn];
int root,tot;
struct Light 
{
	int num,staus;
};
Light A[maxn>>1];
int __gcd(int a,int b){
	int t;
	while(a&&b){
		t=b;
		b=a%b;
		a=t;
	}
	return a+b;
}
void newnode(int &x,int fa,int k,int staus)
{
	x=++tot;
	siz[x]=1;
	pre[x]=fa;
	key[x]=k;
	ch[x][1]=ch[x][0]=0;
	gcd[x][0]=gcd[x][1]=0;
	gcd[x][rev[x]=staus]=x;
}
void push_up(int x)
{
	siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1;
	gcd[x][0]=__gcd(gcd[ch[x][0]][0],gcd[ch[x][1]][0]);
	gcd[x][1]=__gcd(gcd[ch[x][0]][1],gcd[ch[x][1]][1]);
	gcd[x][rev[x]]=__gcd(gcd[x][rev[x]],key[x]);
}
void Rotate(int x,int kind)
{
	int y=pre[x];
	ch[y][!kind]=ch[x][kind];
	pre[ch[x][kind]]=y;
	ch[x][kind]=y;

	if(pre[y])ch[pre[y]][ch[pre[y]][1]==y]=x;
	pre[x]=pre[y];
	pre[y]=x;
	push_up(y);
	push_up(x);
}
void Splay(int x,int goal)
{
	while(pre[x]!=goal){
		if(pre[pre[x]]==goal)Rotate(x,ch[pre[x]][0]==x);
		else{
			int y=pre[x];
			int kind=(ch[pre[y]][0]==y);
			if(ch[y][kind]==x){
				Rotate(x,!kind);
				Rotate(x,kind);
			}else{
				Rotate(y,kind);
				Rotate(x,kind);
			}
		}
	}
	if(goal==0)root=x;
}
int Get_kth(int x,int k)
{
	int sz=siz[ch[x][0]]+1;
	if(sz==k)return x;
	if(sz>k)return Get_kth(ch[x][0],k);
	return Get_kth(ch[x][1],k-sz);
}
void Modify(int x,int k){
	Splay(Get_kth(root,x),0);
	key[root]=k;
	push_up(root);
}
void update(int x)
{
	Splay(Get_kth(root,x),0);
	rev[root]^=1;
	push_up(root);
}
void Insert(int x,int k,int staus){
	Splay(Get_kth(root,x),0);
	int t_root=ch[root][1];
	newnode(ch[root][1],root,k,staus);
	ch[ch[root][1]][1]=t_root;
	pre[t_root]=ch[root][1];
	push_up(ch[root][1]);
	push_up(root);
}
void Remove(int x){
	Splay(Get_kth(root,x-1),0);
	Splay(Get_kth(root,x+1),root);
	ch[ch[root][1]][0]=0;
	push_up(ch[root][1]);
	push_up(root);
}
void built(int &x,int L,int R,int fa)
{
	if(L>R)return;
	int mid=(R+L)>>1;
	newnode(x,fa,A[mid].num,A[mid].staus);
	built(ch[x][0],L,mid-1,x);
	built(ch[x][1],mid+1,R,x);
	push_up(x);
}
void init(int n)
{
	siz[0]=gcd[0][0]=gcd[0][1]=0;
	key[root=0]=tot=ch[0][0]=ch[0][1]=0;
	for(int i=1;i<=n;i++){
		scanf("%d%d",&A[i].num,&A[i].staus);
	}
	newnode(root,0,0,0);
	newnode(ch[root][1],root,0,0);
	built(ch[ch[root][1]][0],1,n,ch[root][1]);
}
int Query(int L,int R,int staus)
{
	Splay(Get_kth(root,L-1),0);
	Splay(Get_kth(root,R+1),root);
	int x=ch[ch[root][1]][0];
	return gcd[x][staus];
}
int main(int argc, char const *argv[])
{
	int n,Q,L,R,staus;
	while(~scanf("%d%d",&n,&Q)){
		init(n);
		char cmd[5];
		while(Q--){
			scanf("%s",cmd);
			if(cmd[0]=='Q'){
				scanf("%d%d%d",&L,&R,&staus);
				int ans=Query(L+1,R+1,staus);
				if(!ans)ans=-1;
				printf("%d\n",ans);
			}else if(cmd[0]=='D'){
				scanf("%d",&L);
				Remove(L+1);
			}else if(cmd[0]=='I'){
				scanf("%d%d%d",&L,&R,&staus);
				Insert(L+1,R,staus);
			}else if(cmd[0]=='R'){
				scanf("%d",&L);
				update(L+1);
			}else{
				scanf("%d%d",&L,&R);
				Modify(L+1,R);
			}
		}
	}
	return 0;
}