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

oyjpArt ACM/ICPC算法程序設(shè)計空間

// 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) // 獲得點的覆蓋次數(shù)
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   回復(fù)  更多評論   

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

# re: HOJ 11107   回復(fù)  更多評論   

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

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

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

呵呵~~

# re: HOJ 11107   回復(fù)  更多評論   

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

# re: HOJ 11107   回復(fù)  更多評論   

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

# re: HOJ 11107   回復(fù)  更多評論   

2008-10-13 14:14 by re: HOJ 11107
int get(int x) { // 獲得點的覆蓋次數(shù)
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}

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

應(yīng)改為:

int get(int x) { // 獲得點的覆蓋次數(shù)
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   回復(fù)  更多評論   

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

# re: HOJ 11107   回復(fù)  更多評論   

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

# re: HOJ 11107   回復(fù)  更多評論   

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>
            国产精品一级在线| 欧美在线91| 欧美精品在线一区| 日韩天堂在线观看| 亚洲人成亚洲人成在线观看图片 | 小嫩嫩精品导航| 国产伦精品一区二区三区免费| 欧美亚洲系列| 欧美伊人久久| 亚洲国产精品va| 亚洲精品国产拍免费91在线| 国产精品国产馆在线真实露脸| 欧美一区成人| 噜噜噜91成人网| 在线视频日韩精品| 久久成人免费网| 亚洲三级影片| 午夜精品久久久久久久男人的天堂| 国产无一区二区| 亚洲国产一区二区三区高清| 国产精品久久婷婷六月丁香| 美女精品视频一区| 欧美日韩国产精品专区 | 在线观看三级视频欧美| 亚洲精品免费一二三区| 国产欧美日韩专区发布| 欧美激情欧美狂野欧美精品| 国产精品欧美日韩久久| 欧美二区乱c少妇| 国产精品欧美风情| 91久久中文字幕| 韩曰欧美视频免费观看| 日韩午夜三级在线| 1000部国产精品成人观看| 在线视频亚洲欧美| 最新国产拍偷乱拍精品| 午夜精品视频在线| 亚洲一区精品视频| 欧美电影在线| 欧美不卡一卡二卡免费版| 国产精品久久久久久久久久久久久| 麻豆国产精品va在线观看不卡| 欧美午夜一区| 亚洲激情av| 亚洲国产精品一区二区尤物区 | 欧美激情久久久久| 国产综合久久久久久鬼色| 夜夜嗨av色综合久久久综合网| 亚洲第一色在线| 欧美亚洲三级| 欧美一区二区三区视频| 国产精品二区二区三区| 一区二区成人精品| 亚洲天堂成人在线视频| 欧美人与性动交a欧美精品| 亚洲缚视频在线观看| 在线观看国产精品淫| 久久成人综合视频| 久久精品国产第一区二区三区最新章节| 欧美日韩亚洲视频| 亚洲乱码视频| 夜夜嗨一区二区| 欧美日韩一区二区三区在线 | 久久精品国产亚洲5555| 久久精品卡一| 国内外成人免费视频| 欧美一级理论片| 久久久人成影片一区二区三区| 国产一二三精品| 久久久久久黄| 欧美韩日精品| 日韩午夜在线电影| 欧美日韩亚洲一区二区三区四区| 亚洲精品无人区| 亚洲小说欧美另类社区| 国产精品美女| 欧美在线一二三四区| 欧美成人官网二区| 亚洲美女一区| 国产精品草草| 久久久91精品国产一区二区三区| 蜜桃久久精品一区二区| 亚洲精品欧美精品| 欧美四级剧情无删版影片| 亚洲在线中文字幕| 欧美va亚洲va日韩∨a综合色| 亚洲电影自拍| 国产精品久久久久久久久久久久久久| 亚洲欧美日韩另类精品一区二区三区| 久久久国产91| 99国产成+人+综合+亚洲欧美| 国产精品爱啪在线线免费观看| 欧美一级夜夜爽| 亚洲国产高清aⅴ视频| 亚洲欧美日本精品| 精品不卡一区| 国产精品chinese| 久久久亚洲影院你懂的| 日韩视频永久免费观看| 久久精品一区二区三区中文字幕| 亚洲成色www8888| 欧美三级精品| 久久综合九色综合欧美狠狠| 一区二区三区精品久久久| 麻豆精品传媒视频| 亚洲在线成人精品| 亚洲欧洲日本专区| 国产一区二区按摩在线观看| 欧美巨乳在线| 久久久99免费视频| 亚洲午夜精品一区二区三区他趣 | 亚洲美女91| 国产自产精品| 国产精品有限公司| 欧美猛交免费看| 久久久91精品国产一区二区精品| 99国产精品久久久久老师| 欧美.日韩.国产.一区.二区| 欧美亚洲一级| 亚洲一区国产精品| 日韩一本二本av| 亚洲国产欧美在线人成| 狠狠色丁香婷婷综合久久片| 国产精品视频内| 国产精品国产三级国产普通话99| 男女av一区三区二区色多| 久久激情久久| 欧美亚洲视频| 午夜精品久久久久久久久 | 欧美激情中文字幕一区二区| 久久狠狠亚洲综合| 欧美一区二视频| 亚洲欧美成人一区二区在线电影| 制服丝袜激情欧洲亚洲| 亚洲精品婷婷| 亚洲精品在线一区二区| 亚洲欧洲在线免费| 亚洲精品123区| 亚洲日本aⅴ片在线观看香蕉| 樱桃视频在线观看一区| 在线色欧美三级视频| 激情久久综合| 亚洲国产一成人久久精品| 永久久久久久| 亚洲人成久久| 日韩一级黄色片| 一本色道久久综合亚洲精品高清 | 激情综合自拍| 激情成人综合网| 最新成人av网站| 99精品国产在热久久| 亚洲免费在线看| 亚洲欧美日韩国产综合精品二区| 亚洲免费影视| 久久久蜜桃精品| 欧美gay视频| 亚洲日本aⅴ片在线观看香蕉| 亚洲精品乱码久久久久久日本蜜臀| 亚洲激情成人在线| 一区二区三区四区五区在线| 亚洲女同性videos| 久久精品人人爽| 欧美顶级大胆免费视频| 欧美福利视频网站| 欧美亚洲不卡| 国产综合色一区二区三区| 亚洲第一色中文字幕| 亚洲一区图片| 免费久久99精品国产| 亚洲精品社区| 久久疯狂做爰流白浆xx| 欧美成人在线网站| 国产精品一区二区三区乱码| 精品成人一区二区三区四区| 99亚洲精品| 久久亚洲欧美| 日韩午夜高潮| 久久久亚洲国产天美传媒修理工| 欧美日韩伦理在线免费| 国产偷国产偷亚洲高清97cao| 亚洲精品国产品国语在线app| 香蕉久久夜色精品国产| 欧美成人一品| 欧美亚洲一级片| 欧美精品日韩www.p站| 国产一区二区欧美日韩| 中文av字幕一区| 免费久久精品视频| 亚洲深夜激情| 欧美激情精品久久久六区热门 | 加勒比av一区二区| 亚洲一区精品视频| 亚洲精品1区| 午夜激情综合网| 免费h精品视频在线播放| 国产精品高清网站| 亚洲裸体俱乐部裸体舞表演av| 欧美有码在线观看视频| 日韩午夜中文字幕| 欧美jizz19性欧美|