P4868 Preprefix sum

题意

给一个长度 $n$ 的序列 $a$ ，有两种操作（共 $m$ 次）：

把 $a_i$ 改成 $x$ ；
查询 $SS_i$ 。

其中，若 $S_i$ 定义为 $\sum_{j=1}^i a_j$ （前缀和），则 $SS_i$ 定义为 $\sum_{k=1}^i S_k$ （前缀和的前缀和）。

$1\le n,m\le 10^5$ ， $0\le a\le10^5$ 。

点击查看题解

题解

利用线段树维护 $S$ 。

对于操作一，转化为区间 $[i,n]$ 加 $\Delta=data-a_i$ 。

对于操作一，转化为求区间 $[1,i]$ 的和。

X1550 花神游历各国

题意

给一个长度 $n$ 的序列 $a$ ，有两种操作（共 $m$ 次）：

区间 $[l,r]$ 开根号（结果向下取整）；
查询区间 $[l,r]$ 的和。

$1 \le n \le 10^5$ ， $1 \le m \le2\times 10^5$ ， $a_i\le10^9$ 。

点击查看题解

题解

将区间修改改为单点修改。 $10^9$ 不超过 $6$ 次开方并向下取整就变成 $1$ 。为了保证时间复杂度正确，如果线段树节点的子孙都是 $1$ ，就不用再访问了。

代码

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	#define ll long long
	const ll N=100005;ll m,n,b[N];
	struct SGT
	{
		#define ll long long
		#define lson (root*2)
		#define rson ((root*2)+1)
		#define mid ((l+r)/2)
		struct Node
		{
			ll data,tag;
			Node(){tag=0;}//不是 lazytag
		}t[N<<3];
		void pushup(ll root)
		{
			t[root].tag=t[lson].tag&t[rson].tag;
			t[root].data=t[lson].data+t[rson].data;
			return;
		}
		void update(ll root,ll l,ll r,ll x,ll y)
		{
			if(t[root].tag==1) return;
			if(l==r)
			{
				t[root].data=(ll)sqrt((double)t[root].data);
				if(t[root].data<=1) t[root].tag=1;
				return;
			}
			if(x<=mid) update(lson,l,mid,x,y);
			if(y>mid) update(rson,mid+1,r,x,y);
			pushup(root);
		}
		ll query(ll root,ll l,ll r,ll x,ll y)
		{
			if(x<=l&&y>=r) return t[root].data;
			ll ansl=0,ansr=0;
			if(x<=mid) ansl=query(lson,l,mid,x,y);
			if(y>mid) ansr=query(rson,mid+1,r,x,y);
			return ansl+ansr;
		}
		void build(ll root,ll l,ll r,ll d[])
		{
			if(l==r)
			{
				t[root].data=d[l];
				if(t[root].data<=1) t[root].tag=1;
				return;
			}
			build(lson,l,mid,d);
			build(rson,mid+1,r,d);
			pushup(root);
			return;
		}
	}Tree;
	void yzmain()
	{
		ll t1,t2,t3; 
		scanf("%lld",&n);
		for(ll i=1;i<=n;i++) 
			scanf("%lld",b+i);
		Tree.build(1,1,n,b);
		scanf("%lld",&m);
		for(ll i=1;i<=m;i++)
		{
			scanf("%lld%lld%lld",&t1,&t2,&t3);
			if(t1==1)
				printf("%lld\n",Tree.query(1,1,n,t2,t3));
			else
				Tree.update(1,1,n,t2,t3);
		}
		return;
	}
}
int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	_yz::yzmain();
	return 0;
}

P3870 [TJOI2009]开关

题意

给一个长度 $n$ 的序列 $c$ ，有两种操作（共 $m$ 次）：

指定区间 $[l,r]$ ，然后 $\forall i\in[l,r]$ ， $c_i\gets c_i \oplus 1$ ；
指定区间 $[l,r]$ ，询问 $\forall i\in[l,r]$ ， $c_i$ 的值为 $1$ 的个数。

其中 $\oplus$ 指按位异或。初始序列中 $c_i$ 的值都为 $0$ 。

保证 $2\le n\le 10^5$ ， $1\le m\le 10^5$ ， $1\le l,r\le n$ ， $c_i\in\{0,1\}$ 。

点击查看题解

题解

设一个区间 $[l,r]$ 的开灯数量是 $a$ ，则改变状态后，开灯数量变为 $r-l+1-a$ 。

使用 lazytag 来减少不必要的修改，pushdown 时利用异或（改变两次状态相当于不改变）。

代码

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	#define ll long long
	const ll N=100005;ll m,n,a[N];
	struct SGT
	{
		#define ll long long
		#define lson (root*2)
		#define rson ((root*2)+1)
		#define mid ((l+r)/2)
		struct Node{ll data,tag;}t[N<<3];
		void pushdown(ll root,ll l,ll r)
		{
			ll tag=t[root].tag;
			if(t[root].tag==0) return;
			t[lson].data=(mid-l+1)-t[lson].data;
			t[rson].data=(r-mid)-t[rson].data;
			t[lson].tag^=tag;t[rson].tag^=tag;
			t[root].tag^=tag;
			return;
		}
		void update(ll root,ll l,ll r,ll x,ll y,ll data)
		{
			if(x<=l&&y>=r)
			{
				t[root].data=(r-l+1)-t[root].data;
				t[root].tag^=data;
				return;
			}
			pushdown(root,l,r);
			if(x<=mid) update(lson,l,mid,x,y,data);
			if(y>mid) update(rson,mid+1,r,x,y,data);
			t[root].data=t[lson].data+t[rson].data;
		}
		ll query(ll root,ll l,ll r,ll x,ll y)
		{
			if(x<=l&&y>=r) return t[root].data;
			pushdown(root,l,r);
			ll ansl=0,ansr=0;
			if(x<=mid) ansl=query(lson,l,mid,x,y);
			if(y>mid) ansr=query(rson,mid+1,r,x,y);
			return ansl+ansr;
		}
		void build(ll root,ll l,ll r,ll d[])
		{
			if(l==r){t[root].data=d[l];return;}
			build(lson,l,mid,d);
			build(rson,mid+1,r,d);
			t[root].data=t[lson].data+t[rson].data;
			return;
		}
	}Tree;
	void yzmain()
	{
		ll t1,t2,t3;
		scanf("%lld%lld",&n,&m);
		Tree.build(1,1,n,a);
		for(ll i=1;i<=m;i++)
		{
			scanf("%lld%lld%lld",&t1,&t2,&t3);
			if(t1==0)
				Tree.update(1,1,n,t2,t3,1);
			else
				printf("%lld\n",Tree.query(1,1,n,t2,t3));
		}
		return;
	}
}
int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	_yz::yzmain();
	return 0;
}

P4513 小白逛公园

题意

给一个长度 $n$ 的序列 $a$ ，有两种操作（共 $m$ 次）：

把 $a_i$ 改成 $x$ ；
查询区间 $[l,r]$ 的最大子段和。

子段是原序列中连续且非空的一段。最大子段是段中元素和最大的子段。最大子段和是最大子段中的元素和。

$1 \le n \le 5 \times 10^5$ ， $1 \le m \le 10^5$ ， $\operatorname{abs}(x)\le1000$ 。

点击查看题解

题解

在一个区间 $[l,r]$ 中，最大子段的位置有 $3$ 种：在 $[l,mid]$ 区间中，在 $[mid+1,r]$ 区间中，跨越 $mid$ 和 $mid+1$ 。其中， $mid=(l+r)/2$ 。

因此，每个节点维护 $4$ 个值：从左端点开始的最大子段和，从右端点开始的最大子段和，本区间最大子段和，区间和。

考虑向父节点转移。详情见代码中的 pushup() 和 query()。

代码

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	#define ll long long
	const ll N=500005,inf=2147483647;
	ll m,n,a[N];
	struct SGT
	{
		/* 区间包含情况
			--------------|----------|-------------- 
		    右端点最大和     区间和     左端点最大和 
		    |  -----   | 最大子段和 
		*/
		#define ll long long
		#define lson (root*2)
		#define rson ((root*2)+1)
		#define mid ((l+r)/2)
		struct Node{ll left,right,sum,maxn;}t[N<<3];
		void pushup(ll root)
		{
			Node L=t[lson],R=t[rson],ret;
			ret.left=max(L.left,L.sum+R.left);
			ret.right=max(R.right,R.sum+L.right);
			ret.sum=L.sum+R.sum;
			ret.maxn=max(L.maxn,max(R.maxn,L.right+R.left));
			t[root]=ret;
		}
		void update(ll root,ll l,ll r,ll x,ll d)
		{
			if(l==r)
			{
				t[root]=(Node){d,d,d,d};
				return;
			}
			if(x<=mid) update(lson,l,mid,x,d);
			if(x>mid) update(rson,mid+1,r,x,d);
			pushup(root);
		}
		Node query(ll root,ll l,ll r,ll x,ll y)
		{
			Node ret;
			if(x<=l&&y>=r) return t[root];
			if(y<=mid) return query(lson,l,mid,x,y);
			else if(x>mid) return query(rson,mid+1,r,x,y);
			else{
				Node L=query(lson,l,mid,x,y);
				Node R=query(rson,mid+1,r,x,y);
				ret.left=max(L.left,L.sum+R.left);
				ret.right=max(R.right,R.sum+L.right);
				ret.maxn=max(L.maxn,max(R.maxn,L.right+R.left));
				ret.sum=L.sum+R.sum; 
			}
			return ret;
		}
		void build(ll root,ll l,ll r,ll d[])
		{
			if(l==r)
			{
				t[root]=(Node){d[l],d[l],d[l],d[l]};
				return;
			}
			build(lson,l,mid,d);
			build(rson,mid+1,r,d);
			pushup(root);
			return;
		}
	}Tree;
	void yzmain()
	{
		ll t1,t2,t3;
		scanf("%lld%lld",&n,&m);
		for(ll i=1;i<=n;i++) scanf("%lld",a+i);
		Tree.build(1,1,n,a);
		for(ll i=1;i<=m;i++)
		{
			scanf("%lld%lld%lld",&t1,&t2,&t3);
			if(t1==2)
				Tree.update(1,1,n,t2,t3);
			else
			{
				if(t2>t3) swap(t2,t3); 
				printf("%lld\n",Tree.query(1,1,n,t2,t3).maxn);
			}
		}
		return;
	}
}
int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	_yz::yzmain();
	return 0;
}