首页 > 代码库 > ZOJ 3765 splay
ZOJ 3765 splay
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 ith light. The initial status and the value is given also.
- D i - Remove the ith light.
- R i - If ith light is on, turn it off, else turn it on.
- M i x - Modify the value of ith 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, Numi (1 ≤ Numi ≤ 1000000000) and Statusi (0 ≤ Statusi ≤ 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
3 12 27 1 32 0 9 1 Q 1 3 1 I 3 64 0 Q 2 4 0 Q 2 4 1 I 2 43 1 D 5 Q 1 2 1 M 1 35 Q 1 2 1 R 1 R 3 Q 1 2 1
Sample Output
9 32 9 27 35 -1
/*************************************************************************
> File Name: Spaly.cpp
> Author: acvcla
> QQ:
> Mail: acvcla@gmail.com
> Created Time: 2014Äê11ÔÂ16ÈÕ ÐÇÆÚÈÕ 00ʱ14·Ö26Ãë
************************************************************************/
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<cstring>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<cstdlib>
#include<ctime>
#include<set>
#include<math.h>
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;
}ZOJ 3765 splay