提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

A - 敌兵布阵 ——B - I Hate It——C - A Simple Problem with Integers（线段树）

IT with 线段 Problem Simple Integers
2023-09-27 14:26:03 时间
C国的死对头A国这段时间正在进行军事演习，所以C国间谍头子Derek和他手下Tidy又开始忙乎了。A国在海岸线沿直线布置了N个工兵营地,Derek和Tidy的任务就是要监视这些工兵营地的活动情况。由于采取了某种先进的监测手段，所以每个工兵营地的人数C国都掌握的一清二楚,每个工兵营地的人数都有可能发生变动，可能增加或减少若干人手,但这些都逃不过C国的监视。
中央情报局要研究敌人究竟演习什么战术,所以Tidy要随时向Derek汇报某一段连续的工兵营地一共有多少人,例如Derek问:“Tidy,马上汇报第3个营地到第10个营地共有多少人!”Tidy就要马上开始计算这一段的总人数并汇报。但敌兵营地的人数经常变动，而Derek每次询问的段都不一样，所以Tidy不得不每次都一个一个营地的去数，很快就精疲力尽了，Derek对Tidy的计算速度越来越不满:"你个死肥仔，算得这么慢，我炒你鱿鱼!”Tidy想：“你自己来算算看，这可真是一项累人的工作!我恨不得你炒我鱿鱼呢!”无奈之下，Tidy只好打电话向计算机专家Windbreaker求救,Windbreaker说：“死肥仔，叫你平时做多点acm题和看多点算法书，现在尝到苦果了吧!”Tidy说："我知错了。。。"但Windbreaker已经挂掉电话了。Tidy很苦恼，这么算他真的会崩溃的，聪明的读者，你能写个程序帮他完成这项工作吗？不过如果你的程序效率不够高的话，Tidy还是会受到Derek的责骂的.

Input第一行一个整数T，表示有T组数据。
每组数据第一行一个正整数N（N<=50000）,表示敌人有N个工兵营地，接下来有N个正整数,第i个正整数ai代表第i个工兵营地里开始时有ai个人（1<=ai<=50）。
接下来每行有一条命令，命令有4种形式：
(1) Add i j,i和j为正整数,表示第i个营地增加j个人（j不超过30）
(2)Sub i j ,i和j为正整数,表示第i个营地减少j个人（j不超过30）;
(3)Query i j ,i和j为正整数,i<=j，表示询问第i到第j个营地的总人数;
(4)End 表示结束，这条命令在每组数据最后出现;
每组数据最多有40000条命令
Output对第i组数据,首先输出“Case i:”和回车,
对于每个Query询问，输出一个整数并回车,表示询问的段中的总人数,这个数保持在int以内。
Sample Input

1
10
1 2 3 4 5 6 7 8 9 10
Query 1 3
Add 3 6
Query 2 7
Sub 10 2
Add 6 3
Query 3 10
End

Sample Output

Case 1:
6
33
59

注意：

1、在查询query函数中，里面两个判断条件之间没有关系，不要使用“else”来使他们联系在一起

2、注意在点修改中只要查到了那个修改的点，修改完要加上“return”

点修改用else，区间修改和区间查询不用else

错的我绝望。。。。。。

上代码：

  1 #include<stdio.h>
  2 #include<string.h>
  3 #include<iostream>
  4 #include<algorithm>
  5 #include<queue>
  6 #include<stack>
  7 #include<vector>
  8 using namespace std;
  9 #define lson l,m,rt<<1
 10 #define rson m+1,r,rt<<1|1
 11 const int INF=0x3f3f3f3f;
 12 const int maxn=50005;
 13 int sum[maxn<<2],add[maxn<<2];
 14 int v[maxn],n;
 15 void pushup(int root) //统计每个点下一级左右分支的和
 16 {
 17     sum[root]=sum[root<<1]+sum[root<<1|1];
 18 }
 19 void build(int l,int r,int root)
 20 {
 21     if(l==r)  //当l==r的是侯就代表树到达了底部，此时既可以对他赋值，其中l，r是
 22     {
 23         //代表这个位置存的值对应的区间
 24         scanf("%d",&sum[root]);
 25         return;
 26     }
 27     int mid=(l+r)>>1;
 28     build(l,mid,root<<1);
 29     build(mid+1,r,root<<1|1);
 30     pushup(root);
 31 }
 32 //点修改
 33 void update(int l,int p,int ll,int rr,int root)//这个l代表要修改的值
 34 {
 35     if(ll==rr)
 36     {
 37         sum[root]+=p;
 38         return; //这里没有加return
 39     }
 40     int mid=(ll+rr)>>1;
 41     //这里要判断一下，保证你递归的区间中包含这个要修改的点
 42     if(l<=mid) update(l,p,ll,mid,root<<1); //注意这里是<=,等于号
 43     else update(l,p,mid+1,rr,root<<1|1);
 44     pushup(root);//更新完子节点之后不要忘记更新父节点
 45 }
 46 //下推标记
 47 void pushdown(int root,int ln,int rn) //ln、rn为左右子树上数字的数量
 48 {
 49     if(add[root])
 50     {
 51         add[root<<1]+=add[root];
 52         add[root<<1|1]+=add[root];
 53         sum[root<<1]+=add[root]*ln;
 54         sum[root<<1|1]+=add[root]*rn;
 55         //消除父节点标记
 56         add[root]=0;
 57     }
 58 }
 59 //更新区间，本题不涉及
 60 void Update(int l,int r,int p,int ll,int rr,int root)
 61 {
 62     if(l<=ll && r<=rr) //满足这个条件就说明这个区间都在我们要修改的区间中
 63     {
 64         sum[root]+=(rr-ll+1)*p;
 65         add[root]+=p; //标记父节点，不能只更新父节点不更新子节点，要记录下来，一旦有机会就要更新
 66         return;
 67     }
 68     int mid=(ll+rr)>>1;
 69     pushdown(root,mid-ll+1,rr-mid);
 70     //这里要判断要递归的区间必须要和我们要修改的区间有交集
 71     if(l<=mid) Update(l,r,p,ll,mid,root<<1);
 72     if(rr>mid) Update(l,r,p,mid+1,rr,root<<1|1);
 73     pushup(root);
 74 }
 75 int query(int L,int R,int l,int r,int rt)
 76 {
 77 //    if(L<=l && R>=r)
 78 //    {
 79 //        return sum[rt];
 80 //    }
 81     if(L <= l && r <= R){
 82 
 83         return sum[rt];
 84 
 85     }
 86     int m=(l+r)>>1;
 87     //在查询之前要往下推标记，要不然可以有些区间没有及时更新
 88     //pushdown(rt,mid-l+1,r-mid);
 89     int ans=0;
 90 //    if(L<=m) ans+=query(L,R,lson);
 91 //    else if(R>m) ans+=query(L,R,rson);
 92 //    return ans;
 93     if(L <= m)
 94 
 95         ans += query(L,R,lson);
 96 
 97     if(R > m)   //上一个条件和下一个条件没有关系，所以这里不能用else
 98                 //找了半天<_>..............................................
 99         ans += query(L,R,rson);
100 
101     return ans;
102 }
103 int main()
104 {
105     int t,k=0,n;
106     char e[15];
107     char q[5][15]={
108         "Query",
109         "Add",
110         "Sub",
111         "End",
112     };
113     scanf("%d",&t);
114     while(t--)
115     {
116         memset(sum,0,sizeof(sum));
117         memset(add,0,sizeof(add));
118         memset(v,0,sizeof(v));
119         k++;
120         printf("Case %d:\n",k);
121         scanf("%d",&n);
122         build(1,n,1);
123         while(1)
124         {
125             scanf("%s",e);
126             if(strcmp(e,q[0])==0)
127             {
128                 int l,r;
129                 scanf("%d%d",&l,&r);
130                 int sum=query(l,r,1,n,1);  //这里的查询写错了
131                 printf("%d\n",sum);  //要查询的区间要写在前面，在那里查询写在后面T_T
132             }
133             else if(strcmp(e,q[1])==0)
134             {
135                 int l,r;
136                 scanf("%d%d",&l,&r);
137                 update(l,r,1,n,1);
138             }
139             else if(strcmp(e,q[2])==0)
140             {
141                 int l,r;
142                 scanf("%d%d",&l,&r);
143                 update(l,-r,1,n,1);
144             }
145             else if(strcmp(e,q[3])==0)
146             {
147                 break;
148             }
149         }
150     }
151     return 0;
152 }
View Code

 B - I Hate It

很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。
这让很多学生很反感。

不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。

Input本题目包含多组测试，请处理到文件结束。
在每个测试的第一行，有两个正整数 N 和 M ( 0<N<=200000,0<M<5000 )，分别代表学生的数目和操作的数目。
学生ID编号分别从1编到N。
第二行包含N个整数，代表这N个学生的初始成绩，其中第i个数代表ID为i的学生的成绩。
接下来有M行。每一行有一个字符 C (只取'Q'或'U') ，和两个正整数A，B。
当C为'Q'的时候，表示这是一条询问操作，它询问ID从A到B(包括A,B)的学生当中，成绩最高的是多少。
当C为'U'的时候，表示这是一条更新操作，要求把ID为A的学生的成绩更改为B。
Output对于每一次询问操作，在一行里面输出最高成绩。Sample Input

5 6
1 2 3 4 5
Q 1 5
U 3 6
Q 3 4
Q 4 5
U 2 9
Q 1 5

Sample Output

5
6
5
9

Hint

Huge input,the C function scanf() will work better than cin

这一道题就是pushup函数改变了，因为要求的是最大值，所以我们在子节点父节点中存的也应该是我们最终的目标

代码：

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<queue>
 6 #include<stack>
 7 #include<vector>
 8 using namespace std;
 9 #define lson l,m,rt<<1
10 #define rson m+1,r,rt<<1|1
11 const int INF=0x3f3f3f3f;
12 const int maxn=200005;
13 int sum[maxn<<2],add[maxn<<2];
14 void pushup(int rt)
15 {
16     sum[rt]=max(sum[rt<<1],sum[rt<<1|1]);
17 }
18 void build(int l,int r,int rt)
19 {
20     if(l==r)
21     {
22         scanf("%d",&sum[rt]);
23         return;
24     }
25     int m=(l+r)>>1;
26     build(l,m,rt<<1);
27     build(m+1,r,rt<<1|1);
28     pushup(rt);
29 }
30 void update(int pos,int c,int l,int r,int rt)
31 {
32     if(l==r)
33     {
34         sum[rt]=c;
35         return;
36     }
37     int m=(l+r)>>1;
38     if(pos<=m) update(pos,c,l,m,rt<<1);
39     else update(pos,c,m+1,r,rt<<1|1);
40     pushup(rt);
41 }
42 int query(int L,int R,int l,int r,int rt)
43 {
44     if(L<=l && R>=r)
45     {
46         return sum[rt];
47     }
48     int m=(l+r)>>1;
49     int ans=0;
50     if(L<=m) ans=max(ans,query(L,R,l,m,rt<<1));
51     if(R>m) ans=max(ans,query(L,R,m+1,r,rt<<1|1));
52     return ans;
53 }
54 int main()
55 {
56     int n,m;
57     char e[5];
58     while(~scanf("%d%d",&n,&m))
59     {
60         memset(sum,0,sizeof(sum));
61         build(1,n,1);
62         while(m--)
63         {
64             int x,y;
65             scanf("%s",e);
66             scanf("%d%d",&x,&y);
67             if(e[0]=='Q')
68             {
69                 printf("%d\n",query(x,y,1,n,1));
70             }
71             else if(e[0]=='U')
72             {
73                 update(x,y,1,n,1);
74             }
75         }
76     }
77     return 0;
78 }
View Code

 C - A Simple Problem with Integers

You have N integers, A1, A2, ... , AN. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.

Input

The first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000.
The second line contains N numbers, the initial values of A1, A2, ... , AN. -1000000000 ≤ Ai ≤ 1000000000.
Each of the next Q lines represents an operation.
"C a b c" means adding c to each of Aa, Aa+1, ... , Ab. -10000 ≤ c ≤ 10000.
"Q a b" means querying the sum of Aa, Aa+1, ... , Ab.

Output

You need to answer all Q commands in order. One answer in a line.

Sample Input

10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4

Sample Output

4
55
9
15

Hint

The sums may exceed the range of 32-bit integers.

本题是区间修改和上面两个不一样，区间修改就要使用到标记，其次有些人用的是结构体里面存有这个节点区间的左右边界

而我使用的是再传参的时候把边界传给下一个节点，这两种方法都可以

上代码：

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<queue>
 6 #include<stack>
 7 #include<vector>
 8 using namespace std;
 9 #define lson l,m,rt<<1
10 #define rson m+1,r,rt<<1|1
11 const int INF=0x3f3f3f3f;
12 const int maxn=200005;
13 typedef long long ll;
14 ll sum[maxn<<2],add[maxn<<2];
15 void pushup(ll rt)
16 {
17     sum[rt]=sum[rt<<1]+sum[rt<<1|1];
18 }
19 void build(ll l,ll r,ll rt)
20 {
21     if(l==r)
22     {
23         scanf("%lld",&sum[rt]);
24         return;
25     }
26     ll m=(l+r)>>1;
27     build(l,m,rt<<1);
28     build(m+1,r,rt<<1|1);
29     pushup(rt);
30 }
31 void pushdown(ll rt,ll ln,ll rn)
32 {
33     if(add[rt])
34     {
35         add[rt<<1]+=add[rt];
36         add[rt<<1|1]+=add[rt];
37         sum[rt<<1]+=add[rt]*ln;
38         sum[rt<<1|1]+=add[rt]*rn;
39         add[rt]=0;
40     }
41 }
42 void update(ll L,ll R,ll C,ll l,ll r,ll rt)
43 {
44     if(l>=L && r<=R)
45     {
46         sum[rt]+=(r-l+1)*C;  //不要忘了这里是+=
47         add[rt]+=C;
48         return;
49     }
50     ll m=(l+r)>>1;
51     pushdown(rt,m-l+1,r-m);
52     if(L<=m) update(L,R,C,l,m,rt<<1);
53     if(R>m) update(L,R,C,m+1,r,rt<<1|1);
54     pushup(rt);
55 }
56 ll query(ll L,ll R,ll l,ll r,ll rt)
57 {
58     if(L<=l && R>=r)
59     {
60         return sum[rt];
61     }
62     ll m=(l+r)>>1;
63     pushdown(rt,m-l+1,r-m);
64     ll ans=0;
65     if(L<=m) ans+=query(L,R,l,m,rt<<1);
66     if(R>m) ans+=query(L,R,m+1,r,rt<<1|1);
67     return ans;
68 }
69 int main()
70 {
71     ll n,m;
72     char e[5];
73     scanf("%lld%lld",&n,&m);
74     build(1,n,1);
75     while(m--)
76     {
77         scanf("%s",e);
78         if(e[0]=='Q')
79         {
80             ll x,y;
81             scanf("%lld%lld",&x,&y);
82             printf("%lld\n",query(x,y,1,n,1));
83         }
84         else  if(e[0]=='C')
85         {
86             ll x,y,z;
87             scanf("%lld%lld%lld",&x,&y,&z);
88             update(x,y,z,1,n,1);
89         }
90     }
91     return 0;
92 }
View Code

 

相关文章