题目链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1174
分析和思路：没什么难理解的。。（暴力就不再说了这题可以水过。。）
rmq（本质dp）
预处理：
设A[i]是要求区间最值的数列，F[i, j]表示从第i个数起连续2^j个数中的最大值。（DP的状态）
我们把F[i，j]平均分成两段（因为f[i，j]一定是偶数个数字），从 i 到i + 2 ^ (j - 1) - 1为一段，i + 2 ^ (j - 1)到i + 2 ^ j - 1为一段(长度都为2 ^ (j - 1))。用上例说明，当i=1，j=3时就是3,2,4,5 和 6,8,1,2这两段。F[i，j]就是这两段各自最大值中的最大值。于是我们得到了状态转移方程F[i, j]=max（F[i，j-1], F[i + 2^(j-1)，j-1]）。
查询：
假如我们需要查询的区间为(i,j)，那么我们需要找到覆盖这个闭区间(左边界取i，右边界取j)的最小幂（可以重复，比如查询5，6，7，8，9，我们可以查询5678和6789）。
因为这个区间的长度为j - i + 1,所以我们可以取k=log2( j - i + 1)，则有：RMQ(A, i, j)=max{F[i , k], F[ j - 2 ^ k + 1, k]}。
举例说明，要求区间[2，8]的最大值，k = log2（8 - 2 + 1）= 2，即求max(F[2, 2]，F[8 - 2 ^ 2 + 1, 2]) = max(F[2, 2]，F[5, 2])。
感觉rmq就是成倍成倍的压缩空间存值，再找到递推空间关系。
1 #include <iostream> 2 #include <algorithm> 3 #include <cmath> 4 #include <cstdio> 5 using namespace std; 6 const int maxn=1e4+5; 7 int a[maxn],f[10001][15]; 8 int n,x,y; 9 10 void rmq() 11 { 12 for(int i=1;i<=n;i++) f[i][0]=a[i];//长度为0就是本身 13 for(int j=1;j<=15;j++)//2的j次方<=maxn 14 { 15 for(int i=1;i<=n;i++) 16 { 17 if(i+(1<<j)-1<=n)//从i开始长度为1<<j的,所以-1 18 f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);//分成2段长度一样的，对数性质，2倍增加！ 19 } 20 } 21 } 22 23 int main() 24 { 25 cin>>n; 26 for(int i=1;i<=n;i++) cin>>a[i]; 27 rmq(); 28 29 int m; 30 cin>>m; 31 while(m--) 32 { 33 cin>>x>>y; 34 x++; y++; 35 36 int k=log2(y-x+1); 37 int ans=max(f[x][k],f[y-(1<<k)+1][k]);//将区间覆盖完全,用y减保证了不会超过 38 cout<<ans<<endl; 39 } 40 41 return 0; 42 }
线段树
1 #include <iostream> 2 #include <algorithm> 3 #include <stdio.h> 4 using namespace std; 5 const int maxn=1e4+5; 6 int n,a,b,m,ans; 7 struct node 8 { 9 int l,r,w,f; 10 }tree[maxn*4]; 11 12 void build(int k,int ll,int rr)//建树 13 { 14 tree[k].l=ll,tree[k].r=rr; 15 if(tree[k].l==tree[k].r) 16 { 17 scanf("%d",&tree[k].w); 18 return; 19 } 20 int m=(ll+rr)/2; 21 build(k*2,ll,m); 22 build(k*2+1,m+1,rr); 23 tree[k].w=max(tree[k*2].w,tree[k*2+1].w); 24 } 25 26 void ask_interval(int k)//区间查询 27 { 28 if(tree[k].l>=a&&tree[k].r<=b) 29 { 30 ans=max(ans,tree[k].w); 31 return; 32 } 33 int m=(tree[k].l+tree[k].r)/2; 34 if(a<=m) ask_interval(k*2); 35 if(b>m) ask_interval(k*2+1); 36 } 37 38 int main() 39 { 40 scanf("%d",&n); 41 build(1,1,n); 42 scanf("%d",&m); 43 44 for(int i=1;i<=m;i++) 45 { 46 ans=0; 47 scanf("%d%d",&a,&b);//区间查询 48 a++; b++; 49 ask_interval(1); 50 printf("%d ",ans); 51 } 52 53 return 0; 54 }
另一种有返回值参数写法
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 using namespace std; 5 typedef long long ll; 6 const int maxn=1e5+5; 7 int a[maxn]; 8 9 struct node 10 { 11 int l,r,f; 12 ll Max; 13 }tree[maxn*4]; 14 15 void build(int k,int l,int r)//建树 16 { 17 tree[k].l=l; tree[k].r=r; 18 if(l==r) 19 { 20 tree[k].Max=a[l]; 21 return; 22 } 23 else 24 { 25 int mid=(l+r)/2; 26 build(k*2,l,mid); 27 build(k*2+1,mid+1,r); 28 tree[k].Max=max(tree[k*2].Max,tree[k*2+1].Max); 29 } 30 } 31 32 ll query(int k,int l,int r,int posl,int posr)//区间查询 33 { 34 if(l>=posl && r<=posr) return tree[k].Max; 35 else 36 { 37 ll ans1=0,ans2=0; 38 int mid=(l+r)/2; 39 if(posl<=mid) ans1=query(k*2,l,mid,posl,posr); 40 if(posr>mid) ans2=query(k*2+1,mid+1,r,posl,posr); 41 42 return max(ans1,ans2); 43 } 44 } 45 46 int main() 47 { 48 ios::sync_with_stdio(false); cin.tie(0); 49 int n; 50 cin>>n; 51 for(int i=1;i<=n;i++) cin>>a[i]; 52 build(1,1,n); 53 54 int m; 55 cin>>m; 56 while(m--) 57 { 58 int x,y; 59 cin>>x>>y; 60 61 ++x; ++y; 62 cout<<query(1,1,n,x,y)<<endl; 63 } 64 return 0; 65 }
//18.10.21更新上最新线段树标准模板
关键：不管是修改还是查询,都是从1结点(根结点全范围)往下操作
线段树模板1：区间加值，区间求和
题目链接：洛谷线段树1
1 #include <iostream> 2 #include <string> 3 #include <algorithm> 4 #include <iomanip> 5 #include <vector> 6 #include <cstdio> 7 #include <cstring> 8 #include <cmath> 9 using namespace std; 10 typedef long long ll; 11 typedef unsigned long long ull; 12 const int maxn=1e5+5; 13 ll a[maxn]; 14 ll n,m; 15 struct px 16 { 17 ll l; 18 ll r; 19 ll w; 20 ll f; 21 }T[maxn*4]; 22 23 void push_up(ll k) 24 { 25 T[k].w=T[k*2].w+T[k*2+1].w; 26 } 27 28 void push_down(ll k,ll l,ll r) 29 { 30 if(T[k].f==0) return; 31 32 ll mid=(l+r)/2; 33 //1.更新和 34 T[k*2].w=T[k*2].w+(mid-l+1)*T[k].f;//这里要*父结点的标记,因为本身可能含有其它父点的还没用的标记 35 T[k*2+1].w=T[k*2+1].w+(r-mid-1+1)*T[k].f; 36 37 //2.下传标记 38 T[k*2].f=T[k*2].f+T[k].f;//传左儿子标记 39 T[k*2+1].f=T[k*2+1].f+T[k].f;//传右儿子标记 40 41 T[k].f=0;//3.父结点初始化 42 } 43 44 void build(ll k,ll l,ll r) 45 { 46 T[k].l=l; T[k].r=r; 47 if(l==r) 48 { 49 T[k].w=a[l]; 50 return; 51 } 52 53 ll mid=(l+r)/2; 54 build(k*2,l,mid); 55 build(k*2+1,mid+1,r); 56 57 push_up(k); 58 } 59 60 void change(ll k,ll l,ll r,ll posl,ll posr,ll val) 61 { 62 if(posl<=l && r<=posr) 63 { 64 T[k].w=T[k].w+(r-l+1)*val; 65 T[k].f=T[k].f+val; 66 return; 67 } 68 69 push_down(k,l,r);//为了第二次及以后更新时准备,必须把上一次传下来的标记但没用的更新用掉,即是在上一次更新操作后的基础上进行这次更新才是正确答案 70 71 ll mid=(l+r)/2; 72 if(posl<=mid) change(k*2,l,mid,posl,posr,val); 73 if(posr>=mid+1) change(k*2+1,mid+1,r,posl,posr,val); 74 75 push_up(k);//父结点不传标记,直接更新一下就行 76 } 77 78 ll ask(ll k,ll l,ll r,ll posl,ll posr) 79 { 80 if(posl<=l && r<=posr) return T[k].w; 81 82 push_down(k,l,r);//必须在查询前就完成传标记更新左右儿子,这样返回时才是修改后的正确答案 83 84 ll mid=(l+r)/2; 85 ll ls=0,rs=0,ans=0;//左儿子和,右儿子和,最终这个结点和 86 if(posl<=mid) ls=ask(k*2,l,mid,posl,posr); 87 if(posr>=mid+1) rs=ask(k*2+1,mid+1,r,posl,posr); 88 89 ans=ls+rs; 90 return ans; 91 } 92 93 int main() 94 { 95 ios::sync_with_stdio(false); cin.tie(0); 96 97 cin>>n>>m; 98 for(int i=1;i<=n;i++) cin>>a[i]; 99 build(1,1,n); 100 101 while(m--) 102 { 103 int p; 104 cin>>p; 105 106 if(p==1) 107 { 108 ll x,y,k; 109 cin>>x>>y>>k; 110 111 change(1,1,n,x,y,k);//不管是修改还是查询,都是从1结点(根结点全范围)往下操作 112 } 113 else if(p==2) 114 { 115 ll x,y; 116 cin>>x>>y; 117 118 ll ans=ask(1,1,n,x,y); 119 cout<<ans<<endl; 120 } 121 } 122 123 return 0; 124 }
线段树模板2：区间加值，区间乘值，区间求和
题目链接：洛谷P3372线段树2
1 #include <iostream> 2 #include <string> 3 #include <algorithm> 4 #include <iomanip> 5 #include <vector> 6 #include <cstdio> 7 #include <cstring> 8 #include <cmath> 9 using namespace std; 10 typedef long long ll; 11 typedef unsigned long long ull; 12 const int maxn=1e5+5; 13 ll mod; 14 ll a[maxn]; 15 ll n,m; 16 struct px 17 { 18 ll l; 19 ll r; 20 ll sum; 21 ll add; 22 ll mul; 23 }T[maxn*4]; 24 25 void push_up(ll k) 26 { 27 T[k].sum=(T[k*2].sum+T[k*2+1].sum)%mod; 28 } 29 30 void push_down(ll k,ll l,ll r) 31 { 32 if(T[k].add==0 && T[k].mul==1) return; 33 34 ll mid=(l+r)/2; 35 36 T[k*2].sum=T[k*2].sum*T[k].mul%mod;//1.更新和,先算乘法再算加法(因为多乘的都算到加法里面了) 37 T[k*2].sum=(T[k*2].sum+(mid-l+1)*T[k].add)%mod; 38 T[k*2+1].sum=T[k*2+1].sum*T[k].mul%mod; 39 T[k*2+1].sum=(T[k*2+1].sum+(r-mid-1+1)*T[k].add)%mod; 40 41 42 T[k*2].mul=T[k*2].mul*T[k].mul%mod;//2.下传乘标记 43 T[k*2+1].mul=T[k*2+1].mul*T[k].mul%mod; 44 45 T[k*2].add=T[k*2].add*T[k].mul%mod;//3.下传加标记(规则和更新和一样,先乘父标记再加父标记) 46 T[k*2].add=(T[k*2].add+T[k].add)%mod; 47 T[k*2+1].add=T[k*2+1].add*T[k].mul%mod; 48 T[k*2+1].add=(T[k*2+1].add+T[k].add)%mod; 49 50 T[k].add=0;//4.父结点标记初始化 51 T[k].mul=1; 52 } 53 54 void build(ll k,ll l,ll r) 55 { 56 T[k].l=l; T[k].r=r; 57 T[k].mul=1; 58 if(l==r) 59 { 60 T[k].sum=a[l]; 61 return; 62 } 63 64 ll mid=(l+r)/2; 65 build(k*2,l,mid); 66 build(k*2+1,mid+1,r); 67 68 push_up(k); 69 } 70 71 void change1(ll k,ll l,ll r,ll posl,ll posr,ll val) 72 { 73 if(posl<=l && r<=posr) 74 { 75 T[k].sum=T[k].sum*val%mod; 76 T[k].mul=T[k].mul*val%mod; 77 T[k].add=T[k].add*val%mod; 78 return; 79 } 80 81 push_down(k,l,r); 82 83 ll mid=(l+r)/2; 84 if(posl<=mid) change1(k*2,l,mid,posl,posr,val); 85 if(posr>=mid+1) change1(k*2+1,mid+1,r,posl,posr,val); 86 87 push_up(k); 88 } 89 90 void change2(ll k,ll l,ll r,ll posl,ll posr,ll val) 91 { 92 if(posl<=l && r<=posr) 93 { 94 T[k].sum=(T[k].sum+(r-l+1)*val)%mod; 95 T[k].add=(T[k].add+val)%mod; 96 return; 97 } 98 99 push_down(k,l,r); 100 101 ll mid=(l+r)/2; 102 if(posl<=mid) change2(k*2,l,mid,posl,posr,val); 103 if(posr>=mid+1) change2(k*2+1,mid+1,r,posl,posr,val); 104 105 push_up(k); 106 } 107 108 ll ask(ll k,ll l,ll r,ll posl,ll posr) 109 { 110 if(posl<=l && r<=posr) return T[k].sum; 111 112 push_down(k,l,r); 113 114 ll mid=(l+r)/2; 115 ll ls=0,rs=0,ans=0; 116 if(posl<=mid) ls=ask(k*2,l,mid,posl,posr); 117 if(posr>=mid+1) rs=ask(k*2+1,mid+1,r,posl,posr); 118 119 ans=(ls+rs)%mod; 120 return ans; 121 } 122 123 int main() 124 { 125 ios::sync_with_stdio(false); cin.tie(0); 126 127 cin>>n>>m>>mod; 128 for(int i=1;i<=n;i++) cin>>a[i]; 129 build(1,1,n); 130 131 while(m--) 132 { 133 int p; 134 cin>>p; 135 136 if(p==1) 137 { 138 ll x,y,k; 139 cin>>x>>y>>k; 140 141 change1(1,1,n,x,y,k); 142 } 143 else if(p==2) 144 { 145 ll x,y,k; 146 cin>>x>>y>>k; 147 148 change2(1,1,n,x,y,k); 149 } 150 else if(p==3) 151 { 152 ll x,y; 153 cin>>x>>y; 154 155 ll ans=ask(1,1,n,x,y); 156 cout<<ans<<endl; 157 } 158 } 159 160 return 0; 161 }
线段树模板3：区间加值，区间乘值，区间求和，区间平方和
牛客练习赛28B数据结构
1 #include <iostream> 2 #include <string> 3 #include <algorithm> 4 #include <iomanip> 5 #include <vector> 6 #include <cstdio> 7 #include <cstring> 8 #include <cmath> 9 using namespace std; 10 typedef long long ll; 11 typedef unsigned long long ull; 12 const int maxn=1e5+5; 13 ll a[maxn]; 14 ll n,m; 15 struct px 16 { 17 ll l; 18 ll r; 19 ll sum; 20 ll num; 21 ll add; 22 ll mul; 23 }T[maxn*4]; 24 25 void push_up(ll k) 26 { 27 T[k].sum=T[k*2].sum+T[k*2+1].sum; 28 T[k].num=T[k*2].num+T[k*2+1].num; 29 } 30 31 void push_down(ll k,ll l,ll r) 32 { 33 if(T[k].add==0 && T[k].mul==1) return; 34 35 ll mid=(l+r)/2; 36 37 T[k*2].num=T[k*2].num*T[k].mul*T[k].mul+2*T[k*2].sum*T[k].mul*T[k].add+(mid-l+1)*T[k].add*T[k].add; 38 T[k*2+1].num=T[k*2+1].num*T[k].mul*T[k].mul+2*T[k*2+1].sum*T[k].mul*T[k].add+(r-mid-1+1)*T[k].add*T[k].add; 39 40 T[k*2].sum=T[k*2].sum*T[k].mul; 41 T[k*2].sum=T[k*2].sum+(mid-l+1)*T[k].add; 42 T[k*2+1].sum=T[k*2+1].sum*T[k].mul; 43 T[k*2+1].sum=T[k*2+1].sum+(r-mid-1+1)*T[k].add; 44 45 46 T[k*2].mul=T[k*2].mul*T[k].mul; 47 T[k*2+1].mul=T[k*2+1].mul*T[k].mul; 48 49 T[k*2].add=T[k*2].add*T[k].mul; 50 T[k*2].add=T[k*2].add+T[k].add; 51 T[k*2+1].add=T[k*2+1].add*T[k].mul; 52 T[k*2+1].add=T[k*2+1].add+T[k].add; 53 54 T[k].add=0; 55 T[k].mul=1; 56 } 57 58 void build(ll k,ll l,ll r) 59 { 60 T[k].l=l; T[k].r=r; 61 T[k].mul=1; 62 if(l==r) 63 { 64 T[k].sum=a[l]; 65 T[k].num=a[l]*a[l]; 66 return; 67 } 68 69 ll mid=(l+r)/2; 70 build(k*2,l,mid); 71 build(k*2+1,mid+1,r); 72 73 push_up(k); 74 } 75 76 void change1(ll k,ll l,ll r,ll posl,ll posr,ll val) 77 { 78 if(posl<=l && r<=posr) 79 { 80 //T[k*2].num=T[k*2].num*T[k].mul*T[k].mul+2*T[k*2].sum*T[k].mul*T[k].add+T[k].add*T[k].add*(mid-l+1);//原始(推出的最本质的不会错)更新照搬过来也可以,但已知这个点是乘法操作就可以化简一些(就跟求和化简加标记一样只算乘法) 81 T[k].num=T[k].num*val*val; 82 T[k].sum=T[k].sum*val; 83 T[k].mul=T[k].mul*val; 84 T[k].add=T[k].add*val; 85 return; 86 } 87 88 push_down(k,l,r); 89 90 ll mid=(l+r)/2; 91 if(posl<=mid) change1(k*2,l,mid,posl,posr,val); 92 if(posr>=mid+1) change1(k*2+1,mid+1,r,posl,posr,val); 93 94 push_up(k); 95 } 96 97 void change2(ll k,ll l,ll r,ll posl,ll posr,ll val) 98 { 99 if(posl<=l && r<=posr) 100 { 101 T[k].num=T[k].num+2*T[k].sum*val+val*val*(r-l+1); 102 T[k].sum=T[k].sum+(r-l+1)*val; 103 T[k].add=T[k].add+val; 104 return; 105 } 106 107 push_down(k,l,r); 108 109 ll mid=(l+r)/2; 110 if(posl<=mid) change2(k*2,l,mid,posl,posr,val); 111 if(posr>=mid+1) change2(k*2+1,mid+1,r,posl,posr,val); 112 113 push_up(k); 114 } 115 116 ll ask1(ll k,ll l,ll r,ll posl,ll posr) 117 { 118 if(posl<=l && r<=posr) return T[k].sum; 119 120 push_down(k,l,r); 121 122 ll mid=(l+r)/2; 123 ll ls=0,rs=0,ans=0; 124 if(posl<=mid) ls=ask1(k*2,l,mid,posl,posr); 125 if(posr>=mid+1) rs=ask1(k*2+1,mid+1,r,posl,posr); 126 127 ans=ls+rs; 128 return ans; 129 } 130 131 ll ask2(ll k,ll l,ll r,ll posl,ll posr) 132 { 133 if(posl<=l && r<=posr) return T[k].num; 134 135 push_down(k,l,r); 136 137 ll mid=(l+r)/2; 138 ll ls=0,rs=0,ans=0; 139 if(posl<=mid) ls=ask2(k*2,l,mid,posl,posr); 140 if(posr>=mid+1) rs=ask2(k*2+1,mid+1,r,posl,posr); 141 142 ans=ls+rs; 143 return ans; 144 } 145 146 int main() 147 { 148 ios::sync_with_stdio(false); cin.tie(0); 149 150 cin>>n>>m; 151 for(int i=1;i<=n;i++) cin>>a[i]; 152 build(1,1,n); 153 154 while(m--) 155 { 156 int p; 157 cin>>p; 158 159 if(p==3) 160 { 161 ll x,y,k; 162 cin>>x>>y>>k; 163 164 change1(1,1,n,x,y,k); 165 } 166 else if(p==4) 167 { 168 ll x,y,k; 169 cin>>x>>y>>k; 170 171 change2(1,1,n,x,y,k); 172 } 173 else if(p==1) 174 { 175 ll x,y; 176 cin>>x>>y; 177 178 ll ans=ask1(1,1,n,x,y); 179 cout<<ans<<endl; 180 } 181 else if(p==2) 182 { 183 ll x,y; 184 cin>>x>>y; 185 186 ll ans=ask2(1,1,n,x,y); 187 cout<<ans<<endl; 188 } 189 } 190 191 return 0; 192 }
//线段树模板4：区间异或，区间求和
Codeforces，242E-XOR on Segment
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #define rank ra 5 #define pb push_back 6 #define lson rt<<1 7 #define rson rt<<1|1 8 using namespace std; 9 typedef long long ll; 10 const int maxn=100005; 11 int n,m; 12 int a[maxn],sk[30]; 13 ll ans; 14 struct node 15 { 16 int l,r,mid; 17 int bit[25],lazy[25]; //bit记录每一位上1的个数 lazy为标记 18 }t[maxn<<2]; 19 20 void pushup(int rt) //pushup操作 数量直接相加即可 21 { 22 for(int i=1;i<=23;i++) 23 t[rt].bit[i]=(t[lson].bit[i]+t[rson].bit[i]); 24 } 25 26 void pushdown(int rt) //pushdown操作 反转即可 27 { 28 for(int i=1;i<=23;i++) 29 { 30 if(t[rt].lazy[i]) 31 { 32 t[lson].bit[i]=t[lson].r-t[lson].l+1-t[lson].bit[i]; 33 t[lson].lazy[i]^=1; 34 t[rson].bit[i]=t[rson].r-t[rson].l+1-t[rson].bit[i]; 35 t[rson].lazy[i]^=1; 36 t[rt].lazy[i]=0; 37 } 38 } 39 } 40 41 void build(int l,int r,int rt) 42 { 43 int mid=(l+r)>>1; 44 t[rt].l=l,t[rt].r=r; 45 t[rt].mid=mid; 46 if(l==r) 47 { 48 int x=a[l],g=1; 49 while(x) //计算数的二进制位 50 { 51 t[rt].bit[g++]=x%2; 52 x=x/2; 53 } 54 return ; 55 } 56 build(l,mid,lson); 57 build(mid+1,r,rson); 58 pushup(rt); 59 } 60 61 void update(int l,int r,int flag,int rt) 62 { 63 if(l<=t[rt].l&&t[rt].r<=r) 64 { 65 for(int i=1;i<=23;i++) 66 { //难点理解,简单例子1 1,^2助于理解 67 //if(flag&(1<<(i-1))) //判断哪些位需要异或 反转且标记 68 if(flag&sk[i]) //2种写法都行,1快2好理解 69 { 70 t[rt].bit[i]=t[rt].r-t[rt].l+1-t[rt].bit[i]; 71 t[rt].lazy[i]^=1; 72 } 73 } 74 return ; 75 } 76 pushdown(rt); 77 if(l<=t[rt].mid) 78 update(l,r,flag,lson); 79 if(r>t[rt].mid) 80 update(l,r,flag,rson); 81 pushup(rt); 82 } 83 84 void query(int l,int r,int rt) 85 { 86 if(l<=t[rt].l&&t[rt].r<=r) //计算结果 87 { 88 for(int i=1;i<=23;i++) 89 ans+=(ll)t[rt].bit[i]*sk[i]; 90 return ; 91 } 92 pushdown(rt); 93 if(l<=t[rt].mid) 94 query(l,r,lson); 95 if(r>t[rt].mid) 96 query(l,r,rson); 97 pushup(rt); 98 } 99 100 int main() 101 { 102 sk[1]=1; 103 for(int i=2;i<=25;i++) sk[i]=2*sk[i-1];//二次方二进制初始化,常用优化操作方便好理解 104 105 scanf("%d",&n); 106 for(int i=1;i<=n;i++) scanf("%d",&a[i]); 107 build(1,n,1); 108 scanf("%d",&m); 109 110 int g,l,r,x; 111 while(m--) 112 { 113 scanf("%d",&g); 114 if(g==1) 115 { 116 ans=0; 117 scanf("%d%d",&l,&r); 118 query(l,r,1); 119 cout<<ans<<endl; 120 } 121 else 122 { 123 scanf("%d%d%d",&l,&r,&x); 124 update(l,r,x,1); 125 } 126 } 127 128 return 0; 129 }
完。