青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

oyjpArt ACM/ICPC算法程序設計空間

// I am new in programming, welcome to my blog
I am oyjpart(alpc12, 四城)
posts - 224, comments - 694, trackbacks - 0, articles - 6

HOJ 11107

Posted on 2008-01-09 14:11 oyjpart 閱讀(7775) 評論(8)  編輯 收藏 引用 所屬分類: ACM/ICPC或其他比賽
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(00, n-1, laps);
58    }

59    num -= laps*n;
60    if(n->= num) {
61        add(0, x, x+num-11);
62    }

63    else {
64        add(0, x, n-11);
65        add(00, (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}

Feedback

# re: HOJ 11107   回復  更多評論   

2008-05-24 21:25 by terence_zhao
good pro
but cant follow you

# re: HOJ 11107   回復  更多評論   

2008-05-25 20:31 by sicheng[I am oyjpArt]
如果我們把這個環放成直線(準確的說是一個區間)來看的話,放入某一個籃子并且按照順時針旋轉一直放num,相當于在這個區間插入很多條線段。而進一步說,我們可以考慮只有3中線段,比如
區間是[0,4] 從3開始插入長度為11的線段 則可以分成
[3,4]
[0,4] * 2
[0,0]
而逆時針的情況很好處理,如果你現算出最后停在哪個點上,換一下起始點和終點就是順時針了.

最后是線段樹了,我們把所有的線段都分別插入.最后統計詢問中的點上有多少線段覆蓋就可以了.

要進行點的線段覆蓋查詢,有很多種做法,我覺得比較好的就是從葉節點向上到根節點,去疊加覆蓋數就可以了.

呵呵~~

# re: HOJ 11107   回復  更多評論   

2008-06-03 14:01 by w
建樹可以非遞歸話吧

# re: HOJ 11107   回復  更多評論   

2008-10-13 10:57 by re: HOJ 11107
謝謝大牛了,我搞了半天終于弄懂了什么原理哈

# re: HOJ 11107   回復  更多評論   

2008-10-13 14:14 by re: HOJ 11107
int 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}

貌似這里有個錯誤,你的代碼對這組數據通不過:
5 3
C 1 5
Q 1
Q 5

應改為:

int get(int x) { // 獲得點的覆蓋次數
44 int idx = upperbound+x-1, sum = 0;
45 do {
46 sum += T[idx].c;
47 idx -= 1;
if(idx != -1) idx >>= 1;
48 } while(idx >= 0);
49 return sum;
50}

# re: HOJ 11107   回復  更多評論   

2008-10-16 02:30 by oyjpart
Thx!~

# re: HOJ 11107   回復  更多評論   

2009-03-23 20:41 by 成大才子
絕對大牛

# re: HOJ 11107   回復  更多評論   

2009-03-26 00:27 by alpc12
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            欲香欲色天天天综合和网| 亚洲综合电影一区二区三区| 在线午夜精品| 亚洲综合精品四区| 美女日韩欧美| 亚洲精品国产欧美| 一区二区三区波多野结衣在线观看| 蜜臀av在线播放一区二区三区| 久久久久久亚洲精品中文字幕| 欧美激情91| 国产日韩欧美不卡| 亚洲激情在线激情| 久久爱另类一区二区小说| 欧美高清视频一二三区| 亚洲与欧洲av电影| 欧美电影美腿模特1979在线看| 国产精品性做久久久久久| 亚洲国产黄色片| 久久久91精品国产一区二区三区 | 国产欧美在线| 亚洲图片在线观看| 亚洲国产日本| 久久xxxx精品视频| 午夜久久黄色| 欧美视频中文一区二区三区在线观看| 一区二区视频欧美| 久久久久国产精品午夜一区| 久久人人爽人人爽爽久久| 国产欧美日韩精品一区| 免费观看成人网| 国产精品日本一区二区| 亚洲第一页在线| 欧美成人精品在线| 欧美一区国产一区| 一区二区三区免费网站| 欧美精品在线视频| 亚洲欧洲日本一区二区三区| 久久人人爽人人| 久久男人av资源网站| 亚洲一区精品电影| 男同欧美伦乱| 夜色激情一区二区| 亚洲精品久久视频| 极品中文字幕一区| 欧美亚洲一区三区| 激情综合激情| 亚洲欧美日韩国产成人| 国产一区二区高清视频| 久久久综合香蕉尹人综合网| 欧美午夜精品理论片a级按摩| 亚洲一级黄色av| 性欧美暴力猛交另类hd| 亚洲一区二区三区三| 欧美久久视频| 亚洲国产精品成人综合| 亚洲国产视频a| 老司机午夜精品| 亚洲精品免费在线播放| 亚洲日本va午夜在线电影| 樱桃国产成人精品视频| 久久成人精品视频| 久久一区二区精品| 欧美激情bt| 欧美国产视频在线观看| 欧美午夜精品理论片a级按摩| 亚洲欧洲精品天堂一级| 国产欧美日韩视频一区二区三区| 一区二区三区四区在线| 国语自产精品视频在线看一大j8| 欧美高清视频一区| 黄色一区二区三区四区| 亚洲免费激情| 欧美日韩免费观看一区| 香蕉乱码成人久久天堂爱免费| 亚洲一区二区三区高清| 一本色道久久加勒比精品| 免费成人av资源网| 亚洲精品孕妇| 亚洲一品av免费观看| 国产日韩欧美中文| 亚洲制服丝袜在线| 欧美亚洲免费高清在线观看| 欧美视频不卡| 一本一本a久久| 久久国产精品黑丝| 国产主播一区二区三区| 久久国产主播| 免费一级欧美片在线播放| 亚洲成人在线视频播放| 国产精品久久久久久久浪潮网站| 亚洲视频一区二区| 欧美日韩亚洲高清一区二区| 99re热这里只有精品视频| 亚洲欧美在线x视频| 久久欧美中文字幕| 亚洲国产精品久久人人爱蜜臀| 亚洲精选在线| 欧美激情一区二区三区在线视频 | 国产女精品视频网站免费 | 欧美成人免费va影院高清| 亚洲精品日韩综合观看成人91| 欧美理论电影网| 亚洲欧美日韩电影| 欧美xart系列高清| 欧美 日韩 国产一区二区在线视频 | 欧美大片在线观看| 亚洲一区二区精品| 久久一日本道色综合久久| 亚洲国产精品一区二区www| 欧美美女视频| 欧美夜福利tv在线| 欧美成人一区在线| 亚洲在线播放电影| 国模叶桐国产精品一区| 欧美电影免费观看高清| 亚洲砖区区免费| 欧美大片在线看| 亚洲欧美日韩天堂| 午夜伦理片一区| 亚洲二区在线观看| 午夜精品福利视频| 亚洲七七久久综合桃花剧情介绍| 欧美涩涩视频| 免费在线看一区| 性欧美精品高清| av成人黄色| 99精品视频免费观看视频| 国产欧美在线观看一区| 欧美三级在线视频| 欧美黄色aaaa| 久热精品在线| 久久久福利视频| 亚洲国产精品久久人人爱蜜臀 | 国产精品美女久久久久av超清| 欧美成人免费全部| 久久久亚洲影院你懂的| 亚洲男人第一av网站| 亚洲精品视频在线播放| 99国产精品久久久久久久成人热 | 鲁鲁狠狠狠7777一区二区| 中日韩美女免费视频网址在线观看| 欧美福利网址| 麻豆精品视频在线观看| 欧美亚洲一区三区| 亚洲女性喷水在线观看一区| 日韩视频免费观看高清在线视频| 一区二区三区在线观看欧美| 欧美精品久久天天躁| 蜜桃av一区| 麻豆精品国产91久久久久久| 久久岛国电影| 午夜视频在线观看一区二区三区| 久久性天堂网| 乱人伦精品视频在线观看| 欧美在线日韩精品| 欧美在线观看视频一区二区三区| 9l视频自拍蝌蚪9l视频成人| 亚洲激情视频网| 亚洲欧洲精品一区二区三区不卡 | 欧美一级日韩一级| 亚洲欧美日韩一区| 亚洲你懂的在线视频| 亚洲午夜精品17c| 亚洲欧美日韩爽爽影院| 亚洲欧美日韩国产综合在线| 午夜精品久久久久久久99水蜜桃| 亚洲欧美999| 狼人天天伊人久久| 欧美成人黑人xx视频免费观看| 你懂的国产精品| 欧美日韩精品伦理作品在线免费观看| 亚洲视频在线看| 午夜精品一区二区在线观看| 亚洲综合日韩| 午夜久久福利| 欧美日韩国产美| 国产精品播放| 国产一区二区三区免费不卡| 韩国av一区二区三区在线观看| 国产精品女主播| 黑人一区二区| 一本色道88久久加勒比精品| 亚洲视频中文| 浪潮色综合久久天堂| 美女精品一区| 亚洲欧美日韩天堂| 美女露胸一区二区三区| 欧美日本一区二区高清播放视频| 欧美性大战久久久久久久蜜臀| 国产三级欧美三级| 亚洲国产精品免费| 久久狠狠久久综合桃花| 亚洲成人在线视频播放| 亚洲欧洲一区二区在线播放| 午夜精品成人在线视频| 欧美国产日韩一区| 国产视频欧美视频| 夜色激情一区二区| 欧美~级网站不卡| 亚洲男人的天堂在线观看|