首页 > 其他分享 >线段树补充

线段树补充

时间：2023-08-09 14:37:32浏览次数：33  
标签：const matrix 补充 线段 id int sum ll

线段树补充

线段树维护矩阵和

矩阵快速幂

和普通快速幂同理

int M;
struct matrix {
	ll x[M+1][M+1];
	matrix() {
		memset(x,0,sizeof(x));
	}
};
matrix multiply(matrix &a,matrix &b) {
	matrix c;
	for(int i=1; i<=M; i++)
		for(int j=1; j<=M; j++)
			for(int k=1; k<=M; k++)
				c.x[i][j]+=a.x[i][k]*b.x[k][j]%mod;
	return c;
}
matrix addMat(matrix &a,matrix &b){
    matrix c;
    for(int i=1;i<=M;i++)
        for(int j=1;j<=M;j++)
            c.x[i][j]=(a.x[i][j]+b.x[i][j])%mod;
    
}
matrix mpow(matrix a,ll m) { //矩阵a的m次方
	matrix res;
	for(int i=1; i<=M; i++) res.x[i][i]=1; //单位矩阵
	while(m>0) {
		if(m&1) res=multiply(res,a);
		a=multiply(a,a);
		m>>=1;
	}
	return res;
}
void Debug(matrix &a) {
	for(int i=1; i<=M; i++) {
		for(int j=1; j<=M; j++) cout<<a.x[i][j]<<" ";
		cout<<'\n';
	}
}
bool check(matrix a){
	int flag=true;
	for(int i=1;i<=M;i++){
		for(int j=1;j<=M;j++){
			if(i!=j&&a.x[i][j]!=0) flag=false;
			else if(i==j&&a.x[i][j]!=1) flag=false;
		}
	}
	return flag;
}

还没验的板子

matrix Gaussian_elimination(matrix arr)
{
	int i, j, k;
	float W[M][2*M], result[M][M];
	float tem_1, tem_2, tem_3;
 
	// 对矩阵右半部分进行扩增
	for(i = 0;i < M; i++){
		for(j = 0;j < 2 * M; j++){
			if(j<N){
				W[i][j] = (float) arr[i][j];
			}
			else{
				W[i][j] = (float) (j-M == i ? 1:0);
			}
		}
	}
 
	for(i=0;i<N;i++)
	{
		// 判断矩阵第一行第一列的元素是否为0，若为0，继续判断第二行第一列元素，直到不为0，将其加到第一行
		if( ((int) W[i][i]) == 0)
		{ 
			for(j=i+1;j<M;j++)
			{
				if( ((int) W[j][i]) != 0 ) break;
			}
			if(j == M)
			{
				printf("这个矩阵不能求逆");
				break;
			}
			//将前面为0的行加上后面某一行
			for(k=0;k<2*M;k++)
			{
				W[i][k] += W[j][k];
			}
		}
 
		//将前面行首位元素置1
		tem_1 = W[i][i];
		for(j=0;j<2*M;j++)
		{
			W[i][j] = W[i][j] / tem_1;
		}
 
		//将后面所有行首位元素置为0
		for(j=i+1;j<M;j++)
		{
			tem_2 = W[j][i];
			for(k=i;k<2*M;k++)
			{
				W[j][k] = W[j][k] - tem_2 * W[i][k];
			}
		}
	}
 
	// 将矩阵前半部分标准化
	for(i=M-1;i>=0;i--)
	{
		for(j=i-1;j>=0;j--)
		{
			tem_3 = W[j][i];
			for(k=i;k<2*M;k++)
			{
				W[j][k] = W[j][k] - tem_3*W[i][k];
			}
		}
	}
 
	//得出逆矩阵
	for(i=0;i<M;i++)
	{
		for(j=M;j<2*M;j++)
		{
			result[i][j-M] = W[i][j];
		}
	}
	return result;
}

对某个数的重复操作可以用矩阵乘法来维护

比如说 要把A，B中的A变成A+B， 就可以对
$$
\left[
\begin{matrix}
A & B\
\end{matrix}
\right]
$$
右乘一个
$$
\left[
\begin{matrix}
1 & 1 \
0 & 1
\end{matrix}
\right]
$$
矩阵乘法是要有顺序的，在重复的情况下可以用快速幂加速

否则用线段树维护区间的加

模板题1 Addition Robot

Problem - K - Codeforces

1691204770028.png

对于这道题，要有顺序的处理A和B矩阵的乘法顺序

因此可以用线段树维护乘法，一直向右乘就行了

在放懒标记的时候，交换矩阵的对角（

#include<bits/stdc++.h>
#define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN =  1e5+7;
const ll mod = 1e9+7;
const ll inf = 0x3f3f3f3f;
#define int ll
struct matrix {
	ll x[3][3];
	matrix() {
		memset(x,0,sizeof(x));
	}
};
matrix multiply(matrix &a,matrix &b) {
	matrix c;
	for(int i=1; i<=2; i++)
		for(int j=1; j<=2; j++)
			for(int k=1; k<=2; k++)
				c.x[i][j]+=a.x[i][k]*b.x[k][j]%mod;
	return c;
}
matrix mpow(matrix &a,ll m) { //矩阵a的m次方
	matrix res;
	for(int i=1; i<=2; i++) res.x[i][i]=1; //单位矩阵
	while(m>0) {
		if(m&1) res=multiply(res,a);
		a=multiply(a,a);
		m>>=1;
	}
	return res;
}

struct Info {
	matrix x;
};
Info operator +(const Info &a,const Info &b) {
	Info c;
	matrix tmpa,tmpb;
	tmpa=a.x;
	tmpb=b.x;
	c.x=multiply(tmpa,tmpb);
	return c;
}
struct node {
	int lazy;
	Info val;
} seg[MAXN<<2];
void up(int id) {
	seg[id].val=seg[id<<1].val+seg[id<<1|1].val;
}
void settag(int id,int l,int r,int tag) {
	seg[id].lazy^=1;
	swap(seg[id].val.x.x[1][2],seg[id].val.x.x[2][1]);
	swap(seg[id].val.x.x[2][2],seg[id].val.x.x[1][1]);
}
void down(int id,int l,int r) {
	if(seg[id].lazy==0) return;
	int mid=l+r>>1;
	settag(id<<1,l,mid,seg[id].lazy);
	settag(id<<1|1,mid+1,r,seg[id].lazy);
	seg[id].lazy=0;
}

char a[MAXN];
matrix A,B;
void build(int id,int l,int r) {
	if(l==r) {
		if(a[l]=='A')
			seg[id].val.x=A;
		else seg[id].val.x=B;
		seg[id].lazy=0;
		return;
	}
	int mid=l+r>>1;
	build(id<<1,l,mid);
	build(id<<1|1,mid+1,r);
	up(id);
}
void modify(int id,int l,int r,int ql,int qr,int val) {
	if (ql<=l&&r<=qr) {
		settag(id,l,r,val);
		return;
	}
	down(id,l,r);
	int mid =(l+r) >> 1;
	if (qr<=mid)
		modify(id <<1,l,mid,ql,qr,val);
	else if (ql>mid)
		modify(id<<1|1, mid+1,r,ql,qr,val);
	else {
		modify(id<<1,l,mid,ql,qr,val);
		modify(id<<1|1,mid+1,r,ql,qr,val);
	}
	up(id);
}
Info query(int id,int l ,int r,int ql,int qr) {
	if(ql<=l&&r<=qr) {
		return seg[id].val;
	}
	down(id,l,r);
	int mid=l+r>>1;
	if(qr<=mid) return query(id<<1,l,mid,ql,qr);
	else if(ql>mid) return query(id<<1|1,mid+1,r,ql,qr);
	else return query(id<<1,l,mid,ql,qr)+query(id<<1|1,mid+1,r,ql,qr);
}
void solve() {
	A.x[1][1]=1;
	A.x[1][2]=0;
	A.x[2][1]=1;
	A.x[2][2]=1;
	B.x[1][1]=1;
	B.x[1][2]=1;
	B.x[2][1]=0;
	B.x[2][2]=1;
	int n,m;
	cin>>n>>m;
	for(int i=1; i<=n; i++) cin>>a[i];
	build(1,1,n);
	while(m--) {
		int op;
		cin>>op;
		if(op==2) {
			int l,r;
			cin>>l>>r;
			int aa,bb;
			cin>>aa>>bb;
			matrix tmp;
			tmp.x[1][1]=aa;
			tmp.x[1][2]=bb;
			matrix k;
			k=query(1,1,n,l,r).x;
			tmp=multiply(tmp,k);
			cout<<tmp.x[1][1]%mod<<" "<<tmp.x[1][2]%mod<<'\n';
		} else {
			int l,r;
			cin>>l>>r;

			modify(1,1,n,l,r,1);

		}
	}
}
signed main() {
	solve();
}

模板题2 Sasha and Array

Problem - C - Codeforces

  • 1691218843101.png

维护斐波那契数列

乘上一个矩阵可以快速得出斐波那契数列

#include<bits/stdc++.h>
#define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN =  3e5+7;
const ll mod = 1e9+7;
const ll inf = 0x3f3f3f3f;
const ll M=2;
#define int ll
struct matrix {
	ll x[M+1][M+1];
	matrix() {
		memset(x,0,sizeof(x));
	}
};
matrix multiply(matrix &a,matrix &b) {
	matrix c;
	for(int i=1; i<=M; i++)
		for(int j=1; j<=M; j++)
			for(int k=1; k<=M; k++)
				c.x[i][j]+=a.x[i][k]*b.x[k][j]%mod;
	return c;
}
matrix mpow(matrix a,ll m) { //矩阵a的m次方
	matrix res;
	for(int i=1; i<=M; i++) res.x[i][i]=1; //单位矩阵
	while(m>0) {
		if(m&1) res=multiply(res,a);
		a=multiply(a,a);
		m>>=1;
	}
	return res;
}
void Debug(matrix &a) {
	for(int i=1; i<=M; i++) {
		for(int j=1; j<=M; j++) cout<<a.x[i][j]<<" ";
		cout<<'\n';
	}
}
struct Info {
	matrix sum;
};
Info operator +(const Info &a,const Info &b) {
	Info c;
	c.sum.x[1][1]=(a.sum.x[1][1]+b.sum.x[1][1])%mod;
	c.sum.x[1][2]=(a.sum.x[1][2]+b.sum.x[1][2])%mod;
	c.sum.x[2][1]=(a.sum.x[2][1]+b.sum.x[2][1])%mod;
	c.sum.x[2][2]=(a.sum.x[2][2]+b.sum.x[2][2])%mod;
	return c;
}
matrix A;
int a[MAXN];
struct node {
	int lazy;
	Info val;
} seg[MAXN<<2];
void up(int id) {
	seg[id].val=seg[id<<1].val+seg[id<<1|1].val;
}
void settag(int id,int l,int r,int tag) {
	matrix tmp=mpow(A,tag);
	seg[id].val.sum=multiply(seg[id].val.sum,tmp);
	seg[id].lazy+=tag;
}
void down(int id,int l,int r) {
	if(seg[id].lazy==0) return;
	int mid=l+r>>1;
	settag(id<<1,l,mid,seg[id].lazy);
	settag(id<<1|1,mid+1,r,seg[id].lazy);
	seg[id].lazy=0;
}
void build(int id,int l,int r) {
	if(l==r) {
		seg[id].val.sum.x[1][1]=1;
		seg[id].val.sum.x[2][2]=1;
		matrix tmp=mpow(A,a[l]-1);
		seg[id].val.sum=multiply(seg[id].val.sum,tmp);
		seg[id].lazy=0;
		return;
	}
	int mid = l+r>>1;
	build(id<<1,l,mid);
	build(id<<1|1,mid+1,r);
	up(id);
}
void modify(int id,int l,int r,int ql,int qr,int val) {
	if (ql<=l&&r<=qr) {
		settag(id,l,r,val);
		return;
	}
	down(id,l,r);
	int mid =(l+r) >> 1;
	if (qr<=mid)
		modify(id <<1,l,mid,ql,qr,val);
	else if (ql>mid)
		modify(id<<1|1, mid+1,r,ql,qr,val);
	else {
		modify(id<<1,l,mid,ql,qr,val);
		modify(id<<1|1,mid+1,r,ql,qr,val);
	}
	up(id);
}
Info query(int id,int l ,int r,int ql,int qr) {
	if(ql<=l&&r<=qr) {
		return seg[id].val;
	}
	down(id,l,r);
	int mid=l+r>>1;
	if(qr<=mid) return query(id<<1,l,mid,ql,qr);
	else if(ql>mid) return query(id<<1|1,mid+1,r,ql,qr);
	else return query(id<<1,l,mid,ql,qr)+query(id<<1|1,mid+1,r,ql,qr);
}
void solve() {
	int n,m;
	cin>>n>>m;
	for(int i=1; i<=n; i++) {
		cin>>a[i];
	}
	A.x[1][1]=1;
	A.x[1][2]=1;
	A.x[2][1]=1;
	A.x[2][2]=0;
	build(1,1,n);
	while(m--) {
		int op;
		cin>>op;
		if(op==1) {
			int l,r,x;
			cin>>l>>r>>x;
			modify(1,1,n,l,r,x);
		} else {
			int l,r;
			cin>>l>>r;
			matrix tmp =query(1,1,n,l,r).sum;
			matrix ans;
			ans.x[1][1]=1;
			ans=multiply(ans,tmp);
			cout<<ans.x[1][1]%mod<<'\n';
		}
	}
}
signed main() {
	solve();
}

*这题时间卡的好死 感觉写再丑点就要t了

模板题3 Robot Arm

Robot Arm

维护一个(x,y)的贡献矩阵 旋转很容易想到是矩阵的乘（旋转公式

拉长就是矩阵按比例增加

#include<bits/stdc++.h>
#define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN =  3e5+7;
const ll mod = 1e9+7;
const ll inf = 0x3f3f3f3f;
const int M=2;
const double PI = acos(-1);
struct matrix {
	double x[M+1][M+1];
	matrix() {
		memset(x,0,sizeof(x));
	}
	void init() {
		for(int i=1; i<=M; i++)
			for(int j=1; j<=M; j++) {
				if(i==j) x[i][j]=1;
				else x[i][j]=0;
			}
	}
};
void Debug(matrix &a) {
	for(int i=1; i<=M; i++) {
		for(int j=1; j<=M; j++) printf("%.6f ",a.x[i][j]);
		cout<<'\n';
	}
}
matrix multiply(matrix a,matrix b) {
	matrix c;
	for(int i=1; i<=M; i++)
		for(int j=1; j<=M; j++)
			for(int k=1; k<=M; k++)
				c.x[i][j]+=a.x[i][k]*b.x[k][j];
	return c;
}
matrix addMat(matrix &a,matrix &b) {
	matrix c;
	for(int i=1; i<=M; i++)
		for(int j=1; j<=M; j++)
			c.x[i][j]=(a.x[i][j]+b.x[i][j]);
//			Debug(c);
	return c;
}
matrix mpow(matrix a,ll m) { //矩阵a的m次方
	matrix res;
	for(int i=1; i<=M; i++) res.x[i][i]=1; //单位矩阵
	while(m>0) {
		if(m&1) res=multiply(res,a);
		a=multiply(a,a);
		m>>=1;
	}
	return res;
}

struct Info {
	matrix sum;
};
Info operator +(const Info &a,const Info &b) {
	Info c;
	matrix aa,bb;
	aa=a.sum;
	bb=b.sum;
	c.sum=addMat(aa,bb);
	return c;
}
struct node {
	matrix lazy;
	Info val;
} seg[MAXN<<2];
void up(int id) {
	seg[id].val.sum=addMat(seg[id<<1].val.sum,seg[id<<1|1].val.sum);
	matrix tmp = addMat(seg[id<<1].val.sum,seg[id<<1|1].val.sum);
}
void settag(int id,int l,int r,matrix tag) {
	seg[id].val.sum=multiply(seg[id].val.sum,tag);
	seg[id].lazy=multiply(seg[id].lazy,tag);
}
bool check(matrix a){
	int flag=true;
	for(int i=1;i<=M;i++){
		for(int j=1;j<=M;j++){
			if(i!=j&&a.x[i][j]!=0) flag=false;
			else if(i==j&&a.x[i][j]!=1) flag=false;
		}
	}
	return flag;
} 
void down(int id,int l,int r) {
	if(check(seg[id].lazy)) return;
	int mid=l+r>>1;
	settag(id<<1,l,mid,seg[id].lazy);
	settag(id<<1|1,mid+1,r,seg[id].lazy);
	seg[id].lazy.init();
}
void build(int id,int l,int r) {
	seg[id].lazy.init();
	if(l==r) {
		seg[id].val.sum.x[1][1]=1;
		seg[id].val.sum.x[1][2]=0;
		return;
	}
	int mid = l+r>>1;
	build(id<<1,l,mid);
	build(id<<1|1,mid+1,r);
	up(id);
}
matrix make(int val) {
	matrix c;
	c.x[1][1]=cos(val*1.0*PI/180);
	c.x[1][2]=-sin(val*1.0*PI/180);
	c.x[2][1]=sin(val*1.0*PI/180);
	c.x[2][2]=cos(val*1.0*PI/180);
	return c;

}
void modify(int id,int l,int r,int ql,int qr,matrix val) {
	if (ql<=l&&r<=qr) {
		settag(id,l,r,val);
		return;
	}
	down(id,l,r);
	int mid =(l+r) >> 1;
	if (qr<=mid)
		modify(id <<1,l,mid,ql,qr,val);
	else if (ql>mid)
		modify(id<<1|1, mid+1,r,ql,qr,val);
	else {
		modify(id<<1,l,mid,ql,qr,val);
		modify(id<<1|1,mid+1,r,ql,qr,val);
	}
	up(id);
}
void change(int id,int l,int r,int pos,int val) {
	if(r<pos||l>pos) return;
	if(l==r&&l==pos) {
		double len=seg[id].val.sum.x[1][1]*seg[id].val.sum.x[1][1]+seg[id].val.sum.x[1][2]*seg[id].val.sum.x[1][2];
		len=sqrt(len);
		seg[id].val.sum.x[1][1]=(len+val)/len*seg[id].val.sum.x[1][1];
		seg[id].val.sum.x[1][2]=(len+val)/len*seg[id].val.sum.x[1][2];
		return;
	}
	int mid=l+r>>1;
	down(id,l,r);
	change(id<<1,l,mid,pos,val);
	change(id<<1|1,mid+1,r,pos,val);
	up(id);
}
Info query(int id,int l ,int r,int ql,int qr) {
	if(ql<=l&&r<=qr) {
		return seg[id].val;
	}
	down(id,l,r);
	int mid=l+r>>1;
	if(qr<=mid) return query(id<<1,l,mid,ql,qr);
	else if(ql>mid) return query(id<<1|1,mid+1,r,ql,qr);
	else return query(id<<1,l,mid,ql,qr)+query(id<<1|1,mid+1,r,ql,qr);
}
void solve() {
	int n,m;
	scanf("%d%d",&n,&m);
	build(1,1,n);
	for(int i=1; i<=m; i++) {
		int op;
		scanf("%d",&op); 
		if(op==1) {
			int p,v;
			cin>>p>>v;
			change(1,1,n,p,v);
		} else {
			int p,v;
			scanf("%d%d",&p,&v);
			matrix tmp=make(v);
			modify(1,1,n,p,n,tmp);
		}
		matrix tmp = query(1,1,n,1,n).sum;
		printf("%.6f %.6f\n",tmp.x[1][1],tmp.x[1][2]);
	}

}
signed main() {
	
	solve();
}

势能线段树

势能线段树支持一些暴力的改法，本身保证次数不多所以可以暴力修改

在题目的思考过程中 不能被显然t的做法吓跑

应该冷静分析次数 找到势能上可以均摊复杂度的证明方法

（这部分感谢实验室学长的debug以及优化方法

模板题1 Lowbit

1691548798256.png

写的很丑所以又卡时间了orz

#include<bits/stdc++.h>
#define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN =  3e5+7;
const ll mod = 998244353;
const ll inf = 0x3f3f3f3f;

#define int ll
int a[MAXN];
int lowbit(int x) {
	return x&-x;
}
int bitcnt(int x) {
	int cnt=0;
	while(x) {
		x-=lowbit(x);
		cnt++;
	}
	return cnt;
}
struct Info {
	int sum,cnt;
};
Info operator +(const Info &a,const Info &b) {
	Info c;
	c.sum=a.sum+b.sum;
	c.sum%=mod;
	c.cnt=a.cnt+b.cnt;
	return c;
}
struct node {
	int lazy;
	Info val;
} seg[MAXN<<2];
void up(int id) {
	seg[id].val=seg[id<<1].val+seg[id<<1|1].val;
}
void settag(int id,int l,int r,int val) {
	seg[id].val.sum*=val;
	seg[id].val.sum%=mod;
	seg[id].lazy*=val;
	seg[id].lazy%=mod;
}
void down(int id,int l,int r) {
	if(seg[id].lazy==1) return;
	int mid=l+r>>1;
	settag(id<<1,l,mid,seg[id].lazy);
	settag(id<<1|1,mid+1,r,seg[id].lazy);
	seg[id].lazy=1;
}
void build(int id,int l,int r) {
	seg[id].lazy=1;
	if(l==r) {
		seg[id].val.sum=a[l];
		seg[id].val.cnt=bitcnt(a[l]);
		return;
	}
	int mid = l+r>>1;
	build(id<<1,l,mid);
	build(id<<1|1,mid+1,r);
	up(id);
}
void change(int id,int l,int r,int pos) {
	if(r<pos||l>pos) return;
	if(l==r&&l==pos) {
		int k=lowbit(seg[id].val.sum);
		if(seg[id].val.cnt==1)
			seg[id].val.sum*=2,seg[id].val.sum%=mod;
		else seg[id].val.sum+=k,seg[id].val.cnt=bitcnt(seg[id].val.sum);
		return;
	}
	int mid=l+r>>1;
	down(id,l,r);
	change(id<<1,l,mid,pos);
	change(id<<1|1,mid+1,r,pos);
	up(id);
}
void modify(int id,int l,int r,int ql,int qr) {
	if (ql<=l&&r<=qr) {
		if(seg[id].val.cnt==r-l+1)
		settag(id,l,r,2);
		else{
			for(int i=l;i<=r;i++) change(id,l,r,i);
		}
		return;
	}
	down(id,l,r);
	int mid =(l+r) >> 1;
	if (qr<=mid)
		modify(id <<1,l,mid,ql,qr);
	else if (ql>mid)
		modify(id<<1|1, mid+1,r,ql,qr);
	else {
		modify(id<<1,l,mid,ql,qr);
		modify(id<<1|1,mid+1,r,ql,qr);
	}
	up(id);
}

Info query(int id,int l ,int r,int ql,int qr) {
	if(ql<=l&&r<=qr) {
		return seg[id].val;
	}
	down(id,l,r);
	int mid=l+r>>1;
	if(qr<=mid) return query(id<<1,l,mid,ql,qr);
	else if(ql>mid) return query(id<<1|1,mid+1,r,ql,qr);
	else return query(id<<1,l,mid,ql,qr)+query(id<<1|1,mid+1,r,ql,qr);
}
void solve() {
	int n;
	cin>>n;
	for(int i=1; i<=n; i++) cin>>a[i];
	build(1,1,n);
//	cout<<"# \n";
//	for(int i=1;i<=n;i++) cout<<query(1,1,n,i,i).sum<<" "<<query(1,1,n,i,i).cnt<<"\n";
	int q;
	cin>>q;
	while(q--) {
		int op,l,r;
		cin>>op>>l>>r;
		if(op==1) {
			modify(1,1,n,l,r);
		} else {
			cout<<query(1,1,n,l,r).sum%mod<<"\n";
		}
	}
}
signed main() {
	close;
	int t;
	cin>>t;
	while(t--)
		solve();
}

模板题2 花神游历各国

P4145 上帝造题的七分钟 2 / 花神游历各国 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

  • 1691561797454.png

与上题不同 本题主要是由于一个数可以被开方的次数有限

并且对于1 都是无限开方，因此 暴力开方就行了

采用了比较快地写法

#include<bits/stdc++.h>
#define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN =  3e5+7;
const ll mod = 1e9+7;
const ll inf = 0x3f3f3f3f;
#define int ll
int a[MAXN];
struct Info {
	int sum;
	int flag;
};
Info operator +(const Info &a,const Info &b) {
	Info c;
	c.sum=a.sum+b.sum;
	c.flag=(a.flag&b.flag);
	return c;
}
struct node {
	int lazy;
	Info val;
} seg[MAXN<<2];
void up(int id) {
	seg[id].val=seg[id<<1].val+seg[id<<1|1].val;
}
void settag(int id,int l,int r,int tag) {
	;
}
void down(int id,int l,int r) {
	if(seg[id].lazy==0) return;
	int mid=l+r>>1;
	settag(id<<1,l,mid,seg[id].lazy);
	settag(id<<1|1,mid+1,r,seg[id].lazy);
	seg[id].lazy=0;
}
void build(int id,int l,int r) {
	if(l==r) {
		seg[id].val.sum=a[l];
		if(a[l]==1) {
			seg[id].val.flag=1;
		}
		seg[id].lazy=0;
		return;
	}
	int mid = l+r>>1;
	build(id<<1,l,mid);
	build(id<<1|1,mid+1,r);
	up(id);
}
void modify(int id,int l,int r,int ql,int qr,int val) {
	if (ql==l&&r==qr) {
		if(seg[id].val.flag==1) {
			settag(id,l,r,val);
			return;
		}

	}
	if(l==r){
		seg[id].val.sum=sqrt(seg[id].val.sum);
		if(seg[id].val.sum==1) seg[id].val.flag=1;
		return;
	}
	down(id,l,r);
	int mid =(l+r) >> 1;
	if (qr<=mid)
		modify(id <<1,l,mid,ql,qr,val);
	else if (ql>mid)
		modify(id<<1|1, mid+1,r,ql,qr,val);
	else {
		modify(id<<1,l,mid,ql,mid,val);
		modify(id<<1|1,mid+1,r,mid+1,qr,val);
	}
	up(id);
}
Info query(int id,int l ,int r,int ql,int qr) {
	if(ql==l&&r==qr) {
		return seg[id].val;
	}
	down(id,l,r);
	int mid=l+r>>1;
	if(qr<=mid) return query(id<<1,l,mid,ql,qr);
	else if(ql>mid) return query(id<<1|1,mid+1,r,ql,qr);
	else return query(id<<1,l,mid,ql,mid)+query(id<<1|1,mid+1,r,mid+1,qr);
}
void solve() {
	int n;cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	int q;cin>>q;
	build(1,1,n);
	while(q--){
		int op,l,r;cin>>op>>l>>r;
		if(l>r) swap(l,r);
		if(op==0){
			modify(1,1,n,l,r,1);
		}
		else{
			cout<<query(1,1,n,l,r).sum<<"\n"; 
		}
	}
}
signed main() {
	solve();
}

标签：const,matrix,补充,线段,id,int,sum,ll
From： https://www.cnblogs.com/xishuiw/p/17616766.html

相关文章

  • 线段树合并学习笔记
    基本思路线段树合并其实就是简单的暴力合并就可以了。一般是运用于权值线段树。通常是在每个节点都需要要一颗线段树才能维护答案，且有多个节点时，会使用线段树合并。但每个节点所有的权值不能太多，如果都是比较满的二叉树的话，时间复杂度就会很高。通常，加入值的数量跟节点数量在同......
  • 李超线段树学习笔记
    用途李超线段树的用法非常固定，一般就是让你求对于给出的一些线段或直线中，对于某个x最大的y是那个。通常可以用于斜率优化。而其的时间复杂度是\(O(n\logn^2)\)思路注：下文默认是线段，因为直线也只用改一下就行了。我们建立一颗线段树，每个节点保存在当前区间，当x=mid时最大的......
  • 【补充】后端接口处理跨域
    【补充】后端接口处理跨域【1】安装pip3.9installdjango-cors-headers【2】注册appINSTALLED_APPS=(...'corsheaders',...)【3】配置中间件MIDDLEWARE=[...'corsheaders.middleware.CorsMiddleware',...]【4】配置文件配置文......
  • 【补充】前后端交互的三种方式
    【补充】前后端交互的三种方式前后端要打通----》从前端发送ajax---》核心：使用js发送http请求，接收返回使用原生JavaScript发送Ajax请求这是一种传统的方式，通过使用JavaScript的XMLHttpRequest对象来发送和接收数据。开发者需要手动处理请求和响应的各个阶段，包括请......
  • 【标签属性补充】scoped/ref/props
    【一】scoped新建的组件加了scoped，表示样式只在当前组件生效如果不加，子组件都会使用这个样式<stylescoped></style>scoped是Vue.js中的一个样式作用域限定符，用于将样式限制在当前组件中生效，并不会影响子组件或父组件。使用scoped后，样式只会应用于当前组件的......
  • 【补充】使用idea打开可运行没问题的js文件，多处红色波浪线警告
    【补充】使用idea打开可运行没问题的js文件，多处红色波浪线警告【一】问题说明问题主要发现于在pycharm中打开Vue项目发现所有JS文件代码底下都是红色波浪线当我们将鼠标悬停在红色波浪线的代码上时，他会提示JSHint:'export'isonlyavailableinES6(use'esversion:6'......
  • 【补充】箭头函数
    【补充】箭头函数函数写法变简单箭头函数没有自己的this，在箭头函数中使用this，就是它上一层的【1】简解箭头函数是ES6中的语法特性，它提供了一种更简洁的函数定义方式。相比传统函数，箭头函数具有以下特点：简化的语法：箭头函数的语法非常简洁，可以帮助我们更快速地编写函数......
  • 【补充】es6的简写推导
    【补充】es6的简写推导//es6的简写形式vara={"name":"dream","age":19}varb={name:"dream",age:19}//一次简写varname="dream"varage=19varf=function(){}vard={"name":name,"age"......
  • 【补充】vm对象简解
    【补充】vm对象简解<body><divid="app"><!--插值语法--><h1>{{name}}</h1><br><h2>方法中的this对象</h2><button@click="handleClick1">点我</button></div></bod......
  • 【补充】数组的过滤
    【补充】数组的过滤数组.filter(匿名函数，接收一个参数，函数必须返回true/false)返回true则表示该数据保留vararr=['a','at','atom','attoo','be','beyond','cs','csrf']//数组.filer(匿名函数，接受一个参数，函数必须......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99