题目
描述
题目大意
维护一个序列，支持三种操作：
1、修改一段区间，将这段区间内的所有数都一个数。
2、询问区间和。
3、询问区间两两相加的平方和。
思路
显然是一道数据结构题。
毋庸置疑的，这绝对是一棵线段树。
第三个操作还是比较简单的：
所以只需要维护区间和还有区间平方和。
这题中，最讨厌的就是修改操作，好端端的，干嘛要来个位运算！
所以我就是着将所有的位分开来。
然而，搞不了第三个询问……
想了半天后弃疗看题解。
正解
这题正解就是直接暴力，没错，就是暴力。
对于线段树的每一个节点，维护一个值表示这段区间内或起来的和。
在修改的时候，我们就可以通过这个东西来判断这个区间里面是否有需要修改的数。
如果有，就继续往下，将它揪出来，暴力修改。
然后？然后就没了啊……
听起来这个方法的时间很诡异，实际上——
对于个点，每个点一共有个位，又因为修改过一个位之后就再也不可能修改这个位，所以，顶多修改次。
乘上线段树的高度就是次。
所以时间复杂度是
代码
using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 100000
#define BIt 30
#define mo 998244353
inline long long pow2(long long x){return x*x;}
int n;
int a[N+1];
struct Ret{//分别是区间和、区间平方和
long long sum;
int sum2;
};
struct Node{
int o;//表示or值
Ret s;
} d[N*4+1];
void init(int,int,int);
void find(int,int,int,int,int,int);//找被修改区间完全覆盖的点
void change(int,int,int,int);
inline Ret operator+(const Ret &a,const Ret &b){
return {a.sum+b.sum,(a.sum2+b.sum2)%mo};
}
Ret query(int,int,int,int,int);
int main(){
freopen("seg.in","r",stdin);
freopen("seg.out","w",stdout);
scanf("%d",&n);
for (int i=1;i<=n;++i)
scanf("%d",&a[i]);
init(1,1,n);
int T;
scanf("%d",&T);
while (T--){
int op;
scanf("%d",&op);
if (op==1){
int l,r,x;
scanf("%d%d%d",&l,&r,&x);
find(1,1,n,l,r,x);
}
else if (op==2){
int l,r;
scanf("%d%d",&l,&r);
printf("%lld
",query(1,1,n,l,r).sum);
}
else{
int l,r;
scanf("%d%d",&l,&r);
Ret res=query(1,1,n,l,r);
printf("%lld
",(((long long)res.sum2*(r-l+1)%mo+pow2(res.sum%mo)%mo)<<1)%mo);
}
}
return 0;
}
void init(int k,int l,int r){
if (l==r){
d[k].s.sum=d[k].o=a[l];
d[k].s.sum2=(long long)a[l]*a[l]%mo;
return;
}
int mid=l+r>>1;
init(k<<1,l,mid);
init(k<<1|1,mid+1,r);
d[k].o=d[k<<1].o|d[k<<1|1].o;
d[k].s=d[k<<1].s+d[k<<1|1].s;
}
void find(int k,int l,int r,int st,int en,int x){
if (st<=l && r<=en){
change(k,l,r,x);
return;
}
int mid=l+r>>1;
if (st<=mid)
find(k<<1,l,mid,st,en,x);
if (mid<en)
find(k<<1|1,mid+1,r,st,en,x);
d[k].o=d[k<<1].o|d[k<<1|1].o;
d[k].s=d[k<<1].s+d[k<<1|1].s;
}
void change(int k,int l,int r,int x){
if ((d[k].o&x)==d[k].o)
return;
if (l==r){
d[k].s.sum=d[k].o&=x;
d[k].s.sum2=(long long)d[k].o*d[k].o%mo;
return;
}
int mid=l+r>>1;
change(k<<1,l,mid,x);
change(k<<1|1,mid+1,r,x);
d[k].o=d[k<<1].o|d[k<<1|1].o;
d[k].s=d[k<<1].s+d[k<<1|1].s;
}
Ret query(int k,int l,int r,int st,int en){
if (st<=l && r<=en)
return d[k].s;
int mid=l+r>>1;
Ret res={0,0};
if (st<=mid)
res=res+query(k<<1,l,mid,st,en);
if (mid<en)
res=res+query(k<<1|1,mid+1,r,st,en);
return res;
}
总结
数据结构的时间复杂度，不应该只看他每次操作的复杂度，还要看看总共最多的复杂度。尤其是类似一次性修改的东西（就是这个数据修改过一次之后就不能再修改了）。
话说，我突然想起以前的一道题目：
有一道数据结构提，正解是分块的根号做法，题解说，线段树不能做……
我坚持用线段树，最终AC了那题，log做法，吊打标算。风光了一时
当时用的也差不多是这样的思想……