codevs4919 线段树练习4

4919 线段树练习4

时间限制: 1 s

空间限制: 128000 KB

题目描述 Description

给你N个数，有两种操作

1：给区间[a,b]内的所有数都增加X

2：询问区间[a,b]能被7整除的个数

输入描述 Input Description

第一行一个正整数n，接下来n行n个整数，再接下来一个正整数Q，表示操作的个数. 接下来Q行每行若干个整数。如果第一个数是add，后接3个正整数a,b,X，表示在区间[a,b]内每个数增加X,如果是count，表示统计区间[a,b]能被7整除的个数

输出描述 Output Description

对于每个询问输出一行一个答案

样例输入 Sample Input

3 
2 3 4
6
count 1 3
count 1 2
add 1 3 2
count 1 3
add 1 3 3
count 1 3

样例输出 Sample Output

数据范围及提示 Data Size & Hint

10%:1<N<=10,1<Q<=10

30%:1<N<=10000,1<Q<=10000

100%:1<N<=100000,1<Q<=100000

这道题的比较裸，需要思考的只有如何pushup和change信息。

对于线段树里存的元素是一个桶，记录这一段余数为1,2,3,4,5,6,0的分别有多少。

在pushup时只需将ls和rs的桶相加即可（代码11行）

在修改时则只需将数组内的是s[i]元素想右移动s[(i+a)%7]即可.

其他基本与普通线段树无异。

 1 #include<cstdio>
 2 #include<cstring>
 3 #define ls x<<1
 4 #define rs x<<1|1
 5 const int N=100005;
 6 int lazy[N<<2];
 7 struct X
 8 {
 9     int s[7];
10     X() {memset(s,0,sizeof(s));};
11     void pu(const X &a,const X &b)
12     {
13         for(int i=0;i<7;i++)
14             s[i]=a.s[i]+b.s[i];
15     }
16     void gb(int x)
17     {
18         X t;
19         for(int i=0;i<7;i++) t.s[(i+x)%7]=s[i];
20         *this=t;
21     }
22 }tree[N<<2];
23 char c[6];
24 void pd(int x)
25 {
26     if(lazy[x])
27     {
28         lazy[ls]+=lazy[x];
29         lazy[rs]+=lazy[x];
30         tree[ls].gb(lazy[x]);
31         tree[rs].gb(lazy[x]);
32         lazy[x]=0;
33     }
34 }
35 void bu(int l,int r,int x)
36 {
37     if(l==r) 
38     {
39         int a;
40         scanf("%d",&a);
41         tree[x].s[a%7]=1;
42     }
43     else
44     {
45         int mid=(l+r)>>1;
46         bu(l,mid,ls);
47         bu(mid+1,r,rs);
48         tree[x].pu(tree[ls],tree[rs]);
49     }
50 }
51 void chan(int l,int r,int x,int s,int ql,int qr)
52 {
53     if(ql<=l&&qr>=r) lazy[x]+=s,tree[x].gb(s);
54     else
55     {
56         int mid=(l+r)>>1;
57         pd(x);
58         if(mid>=ql) chan(l,mid,ls,s,ql,qr);
59         if(qr>mid) chan(mid+1,r,rs,s,ql,qr);
60         tree[x].pu(tree[ls],tree[rs]);
61     }
62 }
63 int ask(int l,int r,int x,int ql,int qr)
64 {
65     if(ql<=l&&qr>=r) return tree[x].s[0];
66     else
67     {
68         int mid=(l+r)>>1,re=0;
69         pd(x);
70         if(mid>=ql) re+=ask(l,mid,ls,ql,qr);
71         if(qr>mid) re+=ask(mid+1,r,rs,ql,qr);
72         tree[x].pu(tree[ls],tree[rs]);
73         return re;
74     }
75 }
76 int main()
77 {
78     int n,q;
79     scanf("%d",&n);
80     bu(1,n,1);
81     scanf("%d",&q);
82     while(q--)
83     {
84         scanf("%s",c);
85         if(c[0]=='a')
86         {
87             int tj,l,r;
88             scanf("%d%d%d",&l,&r,&tj);
89             chan(1,n,1,tj,l,r);
90         }
91         else
92         {
93             int l,r;
94             scanf("%d%d",&l,&r);
95             printf("%d
",ask(1,n,1,l,r));
96         }
97     }
98     return 0;
99 }