HDU1166 敌兵布阵线段树

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 const int N=4*5*1e4+10;
 6 struct node
 7 {
 8     int l,r,w,f;//w该区间和，f懒惰标记
 9 }tree[N];
10 int x,y,ans;
11 void build(int k,int ll,int rr)//建树，k节点序号,ll左端点，rr右端点
12 {
13     tree[k].l=ll,tree[k].r=rr;
14     if(tree[k].l==tree[k].r)
15     {
16         scanf("%d",&tree[k].w);
17         return;
18     }
19     int m=(ll+rr)/2;
20     build(k*2,ll,m);
21     build(k*2+1,m+1,rr);
22     tree[k].w=tree[k*2].w+tree[k*2+1].w;
23 }
24 void down(int k)//标记下传
25 {
26     tree[k*2].f+=tree[k].f;
27     tree[k*2+1].f+=tree[k].f;
28     tree[k*2].w+=tree[k].f*(tree[k*2].r-tree[k*2].l+1);
29     tree[k*2+1].w+=tree[k].f*(tree[k*2+1].r-tree[k*2+1].l+1);
30     tree[k].f=0;
31 }
32 void change_point(int k)//单点修改
33 {
34     if(tree[k].l==tree[k].r)
35     {
36         tree[k].w+=y;
37         return;
38     }
39     if(tree[k].f) down(k);
40     int m=(tree[k].l+tree[k].r)/2;
41     if(x<=m) change_point(k*2);
42     else change_point(k*2+1);
43     tree[k].w=tree[k*2].w+tree[k*2+1].w;
44 }
45 void ask_interval(int k)//区间查询
46 {
47     if(tree[k].l>=x&&tree[k].r<=y)
48     {
49         ans+=tree[k].w;
50         return;
51     }
52     if(tree[k].f) down(k);
53     int m=(tree[k].l+tree[k].r)/2;
54     if(x<=m) ask_interval(k*2);
55     if(y>m) ask_interval(k*2+1);
56 }
57 int main()
58 {
59     int t;
60 //    freopen("in.txt","r",stdin);
61     scanf("%d",&t);//用cin,cout会超时！
62 
63         for (int ca=1;ca<=t;ca++)//ca案例数
64         {
65             printf("Case %d:
",ca);
66             int n;
67             scanf("%d",&n);
68             build(1,1,n);
69             while (1)
70             {
71                 char ts[12];
72                 scanf("%s",ts);
73                 if (strcmp(ts,"End")==0)//这个判断要放在x,y的输入前！
74                 {
75                     break;
76                 }
77                 scanf("%d %d",&x,&y);
78                 ans=0;//记得清零！
79                 if (strcmp(ts,"Query")==0)
80                 {
81                     ask_interval(1);
82                     printf("%d
",ans);
83                 }
84                 if (strcmp(ts,"Add")==0)
85                 {
86                     change_point(1);
87                 }
88                 if (strcmp(ts,"Sub")==0)
89                 {
90                     y=-y;
91                     change_point(1);
92                 }
93             }
94         }
95 
96     return 0;
97 }
HDU1166 敌兵布阵 线段树

HDU1166 敌兵布阵线段树
