题目大意

维护一个序列，支持三种操作：

1、修改一段区间，将这段区间内的所有数都

a n d

一个数。

2、询问区间和。

3、询问区间两两相加的平方和。

N≤10000N\leq 10000

思路

显然是一道数据结构题。

毋庸置疑的，这绝对是一棵线段树。

第三个操作还是比较简单的：

∑(ai+aj)2=∑ai2+aj2+2aiaj=2∗len∗∑ai2+2∑aiaj=2∗len∗∑ai2+2(∑ai)2\sum{(a_i+a_j)^2} \\ =\sum{a_i^2+a_j^2+2a_ia_j}\\ =2*len*\sum{a_i^2}+2\sum{a_ia_j}\\ =2*len*\sum{a_i^2}+2\left(\sum{a_i}\right)^2

所以只需要维护区间和还有区间平方和。

这题中，最讨厌的就是修改操作，好端端的，干嘛要来个位运算！

所以我就是着将所有的位分开来。

然而，搞不了第三个询问……

想了半天后弃疗看题解。

正解

这题正解就是直接暴力，没错，就是暴力。

对于线段树的每一个节点，维护一个值表示这段区间内或起来的和。

在修改的时候，我们就可以通过这个东西来判断这个区间里面是否有需要修改的数。

如果有，就继续往下，将它揪出来，暴力修改。

然后？然后就没了啊……

听起来这个方法的时间很诡异，实际上——

对于

N

个点，每个点一共有

30

个位，又因为修改过一个位之后就再也不可能修改这个位，所以，顶多修改

30 N

次。

乘上线段树的高度就是

30Nlg⁡N30N\lg N

次。

所以时间复杂度是

O(N\lg N\lg 10^9)

代码

using namespace std;#include 
    
     #include 
     
      #include 
      
       #define N 100000#define BIt 30#define mo 998244353inline 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\n",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\n",(((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
       
        >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