HNOJ Beads

Beads
Time Limit: 1000ms, Special Time Limit:2500ms,Memory Limit:65366KB
Problem description
A game consists of putting beads in boxes. The rules of the game are too complex to describe here, but all you need to know is that keeping track of the number of beans in adjacent boxes are very important to the outcome of the game. You are asked by a friend to write a program to help him win the game every time. At the start of a game, all boxes are empty.
Input
The first line of the input consists of a single number T, the number of games played. Each game start with a line describing B, P and Q, the number of boxes, put requests and query requests, respectively. Then follows P + Q lines with either P i a, saying a beads are put in box number i,or Q i j, a query request for the number of beads in boxes i through j, inclusive.
Output
For each query request, output the number of beads in boxes a through b, inclusive, that are in the boxes at this point of the game.
Sample Input
1
7 5 3
P 2 1
P 3 3
P 4 7
Q 1 4
P 7 6
Q 4 4
P 6 4
Q 1 7

Sample Output
11
7
21

Judge Tips
0 < T 100 0 < B 100000 0 < P 30000 0 < Q <= 30000 0 <= a <= 100 0 < i <= j <= B Note that boxes are 1-indexed. This is an I/O-heavy problem. For Java programmers, this means that you should use BufferedReader for input reading (not Scanner). It is also bene cial to build all output in a StringBuilder before printing in a single print statement.
Problem Source
IDIOPEN 2011 제목 대의: 적나라한 나무 모양 수조 템플릿입니다. 하지만 코드를 할 줄 모르기 때문에 코드 트리를 할 수밖에 없습니다. 첫 번째 코드 트리는 엉킵니다.한 시간 동안 디버깅을 했는데, 곤란하다.사고방식:cover: 삽입된 수가 특정한 구간에 있으면 이 구간의cover는 상응하는 값을 더해야 한다는 것을 나타낸다.나는 무한 디버깅을mid에서 사용하는 것은 선의 한 가지 상황이기 때문에 좌우 트리를 나눌 때mid+1이 없다.곤란하다  program: #include #include #include #include #include using namespace std; int sum; struct node {   int a,b,cover;       }tt[1000000]; void first(int p,int a,int b) {    int mid=(a+b)/2;    tt[p].a=a;    tt[p].b=b;    tt[p].cover=0;    if(a==b)        return ;    first(p*2,a,mid);    first(p*2+1,mid+1,b);      } void insert(int p,int i,int w) {      int mid=(tt[p].a+tt[p].b)/2;    /* if(tt[p].a==a&&tt[p].b==b)         {           tt[p].cover++;                             }*/      if(i>=tt[p].a  && i<=tt[p].b )         {            tt[p].cover+=w;                     }      if(tt[p].a==tt[p].b)         return;      if(i<=mid)         insert(p*2,i,w);      else if(i>=mid+1)         insert(p*2+1,i,w); } void query(int p,int a,int b ) {      int mid=(tt[p].a+tt[p].b)/2;     //cout<=mid+1)//CAOCAO는 바로 여기서 패한다. o(╯□╰)oquery(p*2+1,a,b);     else         {           query(p*2,a,mid);           query(p*2+1,mid+1,b);                        }             } int main() { int test; scanf("%d",&test); while(test--) {      int B,P,Q;    scanf("%d%d%d",&B,&P,&Q);    first(1,1,B);    char oder;int i,w;    for(int k=1;k<=P+Q;k++)    {       getchar();      scanf("%c%d%d",&oder,&i,&w);      if(oder=='P')         insert(1,i,w);      else if(oder=='Q')         {           sum=0;           query(1,i,w);           printf("%d",sum);         }    }            } //system("pause"); return 0; }

좋은 웹페이지 즐겨찾기