• <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>
            posts - 20,  comments - 6,  trackbacks - 0
              1 #include<stdio.h>
              2 #include<string.h>
              3 int value[200005];
              4 struct NODE{
              5     NODE *lchild,*rchild;
              6     int left,right;
              7     int sum;
              8 }mem[100001];
              9 int mempos=0;
             10 NODE *makenode()
             11 {
             12     NODE *p=&mem[mempos++];
             13     memset(p,0,sizeof(p));
             14     return p;
             15 }
             16 void update(NODE *root,int id)
             17 {
             18     if(root->right-root->left==1&&(id==root->right||id==root->left))
             19     {
             20         root->sum=value[root->right]+value[root->left];
             21     }else
             22     {
             23         int mid=(root->left+root->right)/2;
             24         if(id>=mid)
             25         update(root->rchild,id);
             26         if(id<=mid)
             27         update(root->lchild,id);
             28         root->sum=root->rchild->sum+root->lchild->sum-value[mid];
             29     }
             30 }
             31 NODE *build(int beg,int end)
             32 {
             33     NODE * root=makenode();
             34     root->left=beg;
             35     root->right=end;
             36     if(end-beg==1)
             37     {
             38         root->sum=value[beg]+value[end];
             39     }else 
             40     {
             41         int mid=(beg+end)/2;
             42         root->lchild=build(beg,mid);
             43         root->rchild=build(mid,end);
             44         root->sum=root->rchild->sum+root->lchild->sum-value[mid];
             45     }
             46     return root;
             47 }
             48 int get(NODE *root,int beg,int end)
             49 {
             50     if(root->left==beg&&root->right==end)
             51     {
             52         return root->sum;
             53     }
             54         int mid=(root->left+root->right)/2;
             55         if(beg>=mid)
             56         {
             57             return get(root->rchild,beg,end);
             58         }else if(end<=mid)
             59         {
             60             return get(root->lchild,beg,end);
             61         }else 
             62         {
             63             int l=get(root->lchild,beg,mid);
             64             int r=get(root->rchild,mid,end);
             65              return l+r-value[mid];
             66         }
             67 }
             68         
             69 int main()
             70 {
             71     int t,n,i,j,k,ss;
             72     int a,b;
             73     int co;
             74     char qus[20];
             75     scanf("%d",&t);
             76         for(co=1;co<=t;co++)
             77         {
             78             printf("Case %d:\n",co);
             79             scanf("%d",&n);
             80             for(i=1;i<=n;i++)
             81             {
             82                 scanf("%d",&value[i]);
             83             }
             84             getchar();
             85             mempos=0;
             86             NODE *root=build(1,n);
             87             while(scanf("%s",qus))
             88             {
             89                 if(strcmp(qus,"End")==0)
             90                 {
             91                     break;
             92                 }
             93                 if(strcmp(qus,"Add")==0)
             94                 {
             95                     scanf("%d%d",&a,&b);
             96                     value[a]+=b;
             97                     update(root,a);
             98                 }
             99                 if(strcmp(qus,"Sub")==0)
            100                 {
            101                     scanf("%d%d",&a,&b);
            102                     value[a]-=b;
            103                     update(root,a);
            104                 }
            105                 if(strcmp(qus,"Query")==0)
            106                 {
            107                     scanf("%d%d",&a,&b);
            108                     ss=get(root,a,b);
            109                     printf("%d\n",ss);
            110                 }
            111             }
            112         }
            113     
            114 }
            115 //寫了一下午,終于用線段樹寫出了1166~ 

            posted on 2009-02-14 16:08 混沌的云 閱讀(224) 評論(0)  編輯 收藏 引用
            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            常用鏈接

            留言簿(1)

            隨筆檔案

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            91精品国产综合久久香蕉| 久久综合久久综合久久综合| 怡红院日本一道日本久久 | 国产99久久久久久免费看| 精品午夜久久福利大片| 国产国产成人久久精品| 99久久香蕉国产线看观香| 亚洲国产另类久久久精品黑人 | 一本一本久久A久久综合精品 | 久久久久这里只有精品| 无码人妻久久一区二区三区免费| 成人综合伊人五月婷久久| 久久亚洲国产成人影院网站| 久久99热只有频精品8| 亚洲国产精品无码久久青草| 国产精品9999久久久久| 免费无码国产欧美久久18| 国产精品无码久久久久| 久久AV高清无码| 一本色道久久综合亚洲精品| 久久久久香蕉视频| 成人亚洲欧美久久久久| 久久er热视频在这里精品| 亚洲国产精品无码久久久秋霞2| 久久精品?ⅴ无码中文字幕| 国产精品青草久久久久婷婷| 亚洲国产精品无码久久SM | 91久久婷婷国产综合精品青草| 欧美精品国产综合久久| 色偷偷91久久综合噜噜噜噜| 97久久精品人人做人人爽| 色偷偷久久一区二区三区| 99久久国产综合精品女同图片| 亚洲精品WWW久久久久久| 四虎国产精品成人免费久久| 久久久无码精品午夜| 99久久精品免费国产大片| 91精品国产91久久久久久青草| 国产成人精品久久二区二区| 国产亚洲欧美精品久久久| 久久精品国产亚洲AV无码麻豆|