| Number of stones |
| Time Limit: 3000ms, Special Time Limit:7500ms, Memory Limit:32768KB |
| Total submit users: 13, Accepted users: 1 |
| Problem 11107 : No special judgement |
| Problem description |
There are N baskets rounded in a circle, and numbered as 1、2、3、…….、N-1、N, in clockwise. At the beginning, all of the baskets are empty. Some workers go to the moutain to collect stones. When they are back,they put their stones to some baskets. The workers have a habit, Once a worker come back, he choose a baskets, and choose a direction(clockwise or anticlockwise), he put one stone to this basket and move to the next basket according to the direction he has chosen, he continues doing this until all of the stones they have collected have been put down.
Sometimes the workers ask you how many stone it is in the basket, as there are too many baskets, You are to wirte a program to calculate this.
|
| Input |
The input test file will contain multiple cases. Each test case:
In the first line of the input contain two integers N,M(3 <= N <= 100000, 0 <= M <= 300000). Following M lines,each line represents an event. There are only three kinds of events: Q, C, U. And the format is:
“Q x”, query the number of stones in the basket x.
“C x num”, a worker comes back and the number of the stones he has picked up is num, he puts down stones from the basket x in clockwise.
“U x num”, a worker comes back and the number of the stone he has picked up is num, he puts down stones from the basket x in anticlockwise.
(x, num are both integers, 1 <= x <= N, 1 <= num <= 10000)
|
| Output |
For each query “Q x”, print the current number of stones in basket x.
|
| Sample Input |
5 8
C 5 8
Q 5
Q 4
U 5 3
C 2 6
Q 2
Q 1
U 2 8
|
| Sample Output |
2
1
4
3
|
| Problem Source |
birdman
|
上次比赛没有做..补做一个..挺好的题..重写了点树模板
1  /**//*
2 * 主程序要作的事情
3 * 1.确定N ：必须是2^n，可以取实际n的上界
4 * 2.build(left, right);
5 *
6 */
7
8#include <cstdio>
9#include <cstring>
10
11const int N = 131072; //必须是2^n，可以取实际n的上界
12
13int upperbound;
14
15struct Node  {
16 int i, j, c, m; //left, right
17} T[N*2];
18
19void bd(int d, int left, int right) {
20 T[d].i = left, T[d].j = right, T[d].c = 0;
21  if(right > left) {
22 bd(d*2+1, left, T[d].m = (left+right)>>1);
23 bd(d*2+2, T[d].m+1, right);
24 }
25}
26
27void build(int left, int right) {
28 upperbound = 1;
29 while(upperbound < right-left+1) upperbound <<= 1;
30 bd(0, left, left + upperbound-1);
31}
32
33void add(int d, int left, int right, int c) {
34 if(left <= T[d].i && right >= T[d].j) {
35 T[d].c += c;
36 }
37 else {
38 if(left <= T[d].m) add(d*2+1, left, right, c);
39 if(right > T[d].m) add(d*2+2, left, right, c);
40 }
41}
42
43int get(int x) { // 获得点的覆盖次数
44 int idx = upperbound+x-1, sum = 0;
45 do {
46 sum += T[idx].c;
47 idx = (idx-1)>>1;
48 } while(idx != 0);
49 return sum;
50}
51
52int n, m;
53
54void Add(int x, int num) {
55 int laps = (num-(n-x))/n;
56 if(laps > 0) {
57 add(0, 0, n-1, laps);
58 }
59 num -= laps*n;
60 if(n-x >= num) {
61 add(0, x, x+num-1, 1);
62 }
63 else {
64 add(0, x, n-1, 1);
65 add(0, 0, (x+num-1)%n, 1);
66 }
67}
68
69int main() {
70 while(scanf("%d %d", &n, &m) != EOF) {
71 build(0, n-1);
72 while(m--) {
73 char cmd;
74 int x, num;
75 scanf(" %c", &cmd);
76 if(cmd == 'Q') {
77 scanf("%d", &x);
78 --x;
79 printf("%d\n", get(x));
80 }
81 else if(cmd == 'C') {
82 scanf("%d %d", &x, &num);
83 --x;
84 Add(x, num);
85 }
86 else if(cmd == 'U') {
87 scanf("%d %d", &x, &num);
88 --x;
89 int y = (x-num+1) % n;
90 if(y < 0) y += n;
91 Add(y, num);
92 }
93 }
94 }
95
96 return 0;
97}
|