首页 > 代码库 > ZOJ3765---Lights (Splay伸展树)
ZOJ3765---Lights (Splay伸展树)
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 1227 132 09 1Q 1 3 1I 3 64 0Q 2 4 0Q 2 4 1I 2 43 1D 5Q 1 2 1M 1 35Q 1 2 1R 1R 3Q 1 2 1
Sample Output
93292735-1
继续splay大法，熟练了之后 这种题就算是裸题了。。。 基本上都会用到 旋转 rotate， 伸展splay，获取第k的元素的位置 Get_kth,翻转reverse，删除delete函数。
这题因为数组开小TLE一上午，昨天晚上明明就已经是正确解法了，害我一直调试。
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 const int maxn = 3e5+100; 7 int siz[maxn],pre[maxn],ch[maxn][2],st[maxn],s[maxn]; 8 int key[maxn],GCD[2][maxn]; 9 int tot1,tot2,root,n,q; 10 int gcd(int x,int y) 11 { 12 return y == 0 ? x : gcd (y,x % y); 13 } 14 void NewNode(int &r,int father,int k,int status) 15 { 16 if (tot2) 17 r = s[tot2--]; 18 else 19 r = ++tot1; 20 pre[r] = father; 21 ch[r][0] = ch[r][1] = 0; 22 st[r] = status; 23 key[r] = k; 24 siz[r] = 1; 25 GCD[0][r] = GCD[1][r] = 0; 26 GCD[st[r]][r] = k; 27 } 28 void push_up(int r) 29 { 30 siz[r] = siz[ch[r][0]] + siz[ch[r][1]] + 1; 31 if (GCD[st[r]][r] == 0) 32 { 33 GCD[st[r]][r] = key[r]; 34 } 35 GCD[0][r] = gcd(GCD[0][ch[r][0]],GCD[0][ch[r][1]]); 36 GCD[1][r] = gcd(GCD[1][ch[r][0]],GCD[1][ch[r][1]]); 37 GCD[st[r]][r] = gcd(GCD[st[r]][r],key[r]); 38 } 39 int A[maxn]; 40 int B[maxn]; // A B 数组分别储存每个light的值以及状态 41 void build(int &x,int l,int r,int father) 42 { 43 if (l > r) 44 return; 45 int mid = (l + r) >> 1; 46 NewNode(x,father,A[mid],B[mid]); 47 build(ch[x][0],l,mid-1,x); 48 build(ch[x][1],mid+1,r,x); 49 push_up(x); 50 } 51 void init() 52 { 53 root = tot1 = tot2 = 0; 54 for (int i = 1; i <= n; i++) 55 scanf ("%d%d",A+i,B+i); 56 NewNode(root,0,1,0); 57 NewNode(ch[root][1],root,1,0); 58 build(ch[ch[root][1]][0],1,n,ch[root][1]); 59 push_up(ch[root][1]); 60 push_up(root); 61 } 62 void Rotate(int x,int kind) 63 { 64 int y = pre[x]; 65 ch[y][!kind] = ch[x][kind]; 66 pre[ch[x][kind]] = y; 67 if (pre[y]) 68 ch[pre[y]][ch[pre[y]][1] == y] = x; 69 pre[x] = pre[y]; 70 ch[x][kind] = y; 71 pre[y] = x; 72 push_up(y); 73 } 74 void Splay(int r,int goal) 75 { 76 while (pre[r] != goal) 77 { 78 if (pre[pre[r]] == goal) 79 { 80 Rotate(r,ch[pre[r]][0] == r); 81 } 82 else 83 { 84 int y = pre[r]; 85 int kind = (ch[pre[y]][1] == y); 86 if (ch[y][kind] == r) 87 { 88 Rotate(y,!kind); 89 Rotate(r,!kind); 90 } 91 else 92 { 93 Rotate(r,kind); 94 Rotate(r,!kind); 95 } 96 } 97 } 98 push_up(r); 99 if (goal == 0)100 root = r;101 }102 int Get_kth(int r,int k)103 {104 int t = siz[ch[r][0]] + 1;105 if (k == t)106 return r;107 if (k > t)108 return Get_kth(ch[r][1],k-t);109 else110 return Get_kth(ch[r][0],k);111 }112 void Insert(int pos,int val,int status)113 {114 Splay(Get_kth(root,pos+1),0);115 Splay(Get_kth(root,pos+2),root);116 NewNode(ch[ch[root][1]][0],ch[root][1],val,status);117 push_up(ch[root][1]);118 push_up(root);119 }120 void eraser(int r)121 {122 if (!r)123 return;124 s[++tot2] = r;125 eraser(ch[r][0]);126 eraser(ch[r][1]);127 }128 void Delete(int pos)129 {130 Splay(Get_kth(root,pos),0);131 Splay(Get_kth(root,pos+2),root);132 eraser(ch[ch[root][1]][0]);133 pre[ch[ch[root][1]][0]] = 0;134 ch[ch[root][1]][0] = 0;135 push_up(ch[root][1]);136 push_up(root);137 }138 void modify (int pos,int val)139 {140 Splay(Get_kth(root,pos),0);141 Splay(Get_kth(root,pos+2),root);142 int key_value = http://www.mamicode.com/ch[ch[root][1]][0];143 key[key_value] = val;144 push_up(ch[ch[root][1]][0]);145 push_up(ch[root][1]);146 push_up(root);147 }148 void reset(int pos)149 {150 Splay(Get_kth(root,pos),0);151 Splay(Get_kth(root,pos+2),root);152 int key_value = http://www.mamicode.com/ch[ch[root][1]][0];153 st[key_value] ^= 1;154 push_up(ch[ch[root][1]][0]);155 push_up(ch[root][1]);156 push_up(root);157 }158 int query(int x,int y,int status)159 {160 Splay(Get_kth(root,x),0);161 Splay(Get_kth(root,y+2),root);162 push_up(ch[ch[root][1]][0]);163 return GCD[status][ch[ch[root][1]][0]];164 }165 int main(void)166 {167 #ifndef ONLINE_JUDGE168 freopen("in.txt","r",stdin);169 #endif170 171 while (~scanf ("%d%d",&n,&q))172 {173 init();174 for (int i = 0; i < q; i++)175 {176 char op[8];177 scanf ("%s",op);178 if (op[0] == ‘Q‘)179 {180 int x,y,z;181 scanf ("%d%d%d",&x,&y,&z);182 int ans = query(x,y,z);183 printf("%d\n",ans > 0 ? ans : -1);184 }185 if (op[0] == ‘I‘)186 {187 int x,z,y;188 scanf ("%d%d%d",&x,&y,&z);189 Insert(x,y,z);190 }191 if (op[0] == ‘D‘)192 {193 int x;194 scanf ("%d",&x);195 Delete(x);196 }197 if (op[0] == ‘M‘)198 {199 int x, z;200 scanf ("%d%d",&x,&z);201 modify(x,z);202 }203 if (op[0] == ‘R‘)204 {205 int x;206 scanf ("%d",&x);207 reset(x);208 }209 }210 }211 return 0;212 }
ZOJ3765---Lights (Splay伸展树)