CF837G - Functions On The Segments

我们考虑 \(\sum_{i=l}^r{f_i(x)}\) 是个什么东西。首先这个奇怪的东西很好离线做，所以尽管题目要求强制在线，我们还是离线下来试试。

我们发现，我们可以 \(x\) 坐标从 \(1\) 到 \(200000\) 扫过去，对于每个 \(f_i\)，在 \(x_{i,1}+1\) 和 \(x_{i,2}+1\) 两个位置打标记进行更改。这样整个扫描过程就是 \(O(k+n)\) 的。然后考虑维护答案，我们发现，\(y=y_1\) 和 \(y=y_2\) 其实可以写成 \(y=0x+y_1,y=0x+y_2\) 的形式。那么，我们的 \(f_i(x)\) 就可以统一写成 \(ax+b\) 的形式。则 \(\sum_{i=l}^r{f_i(x)}=(\sum_{i=l}^r{a_i})x+\sum_{i=l}^r{b_i}\)。

这样，我们就只需要维护 \(a\) 和 \(b\) 的区间和。我们分别开两个线段树维护 \(a\) 和 \(b\) 的区间和。每次更改，就单点修改位置 \(i\) 上面的 \(a_i\) 和 \(b_i\)。然后我们提前把所有的询问挂在自己的 \(x_i\) 上，处理完当前 \(x\) 上的所有操作之后，对所有的 \([l,r]\) 询问进行查询得到 \(\sum_{i=l}^r{a_i}\) 和 \(\sum_{i=l}^r{b_i}\)。

但是现在强制在线，怎么做呢？

我们发现，只要我们存储下每个 \(x\) 所对应的 \(a\) 和 \(b\) 序列，就可以每次快速得到答案。但是存储 \(a\) 和 \(b\) 显然不现实，我们就考虑可持久化线段树。我们找到原先的所有操作：单点修改、区间查询，这恰好是可以使用主席树完成的工作。又因为是静态的，我们完全可以把主席树处理出来之后，带到询问里去计算。

还有一个小小的问题，询问时的 \(x\) 是可能达到 \(10^9\) 的，如何做呢？我们发现 \(2\cdot 10^5\) 之后的 \(x\) 都已经到了第三阶段，也就是 \(y=y_2\)，可以直接处理其前缀和，然后 \(O(1)\) 计算答案。

注意我们同一个 \(x\) 上可能有很多的操作，也可能没有操作，不能把 \(x\) 作为主席树的时间轴，而应当对每个 \(x\) 上的所有操作执行完之后，记录当前主席树的最新版本。

如果我们记 \(k\) 为更改操作中出现的最大 \(x\)，那么时间复杂度就是 \(O(k+(n+m)\log n)\)，空间复杂度 \(O(n\log n)\)。

#define rd(i,n) for(ll i=0;i<n;i++)

#define rp(i,n) for(ll i=1;i<=n;i++)

#define rep(i,a,b) for(ll i=a;i<=b;i++)

typedef long long ll;

class pst{

private:

	ll sum[10000005];

	int ls[10000005],rs[10000005],cnt,Len;

	int root[400005],Ti;

	inline void Init(int &i,int l,int r,int* a){

		i=++cnt;

		if(l==r){

			sum[i]=a[l];

			return;

		}

		int mid=l+r>>1;

		Init(ls[i],l,mid,a);

		Init(rs[i],mid+1,r,a);

		sum[i]=sum[ls[i]]+sum[rs[i]];

	}

	inline void Modify(int &i,int his,int x,int v,int l,int r){

		i=++cnt;

		if(l==r){

			sum[i]=v;

			return;

		}

		int mid=l+r>>1;

		if(x<=mid){

			rs[i]=rs[his];

			Modify(ls[i],ls[his],x,v,l,mid);

		}else{

			ls[i]=ls[his];

			Modify(rs[i],rs[his],x,v,mid+1,r);

		}

		sum[i]=sum[ls[i]]+sum[rs[i]];

	}

	inline ll Query(int i,int L,int R,int l,int r){

		if(!i)return 0;

		if(L<=l&&r<=R)return sum[i];

		int mid=l+r>>1;

		ll res=0;

		if(ls[i]&&L<=mid)res+=Query(ls[i],L,R,l,mid);

		if(rs[i]&&R>mid)res+=Query(rs[i],L,R,mid+1,r);

		return res;

	}

public:

	inline void init(int len,int* a){

		Len=len;

		Init(root[0],1,len,a);

	}

	inline void modify(int x,int v){

		int cnt=++Ti;

		Modify(root[cnt],root[cnt-1],x,v,1,Len);

	}

	inline ll query(int ti,int l,int r){

		return Query(root[ti],l,r,1,Len);

	}

	inline int curver(){

		return Ti;

	}

}ta,tb;

const int N=75005;

const int M=200000;

const int P=1000000000;

int n,m,q,l,r,x,xl[N],xr[N],yl[N],yr[N],a[N],b[N],Empty[N];

ll sum[N];

int vera[M+5],verb[M+5];

vt<int>v1[M+5],v2[M+5];

signed main(){

	ios::sync_with_stdio(false);

	cin.tie(0);

	n=in();

	rp(i,n)xl[i]=in(),xr[i]=in(),yl[i]=in(),a[i]=in(),b[i]=in(),yr[i]=in();

	rp(i,n)v1[xl[i]+1].pb(i),v2[xr[i]+1].pb(i);

	ta.init(n,Empty);tb.init(n,yl);

	rep(ti,1,M){

		for(auto j:v1[ti]){

			ta.modify(j,a[j]);

			tb.modify(j,b[j]);

		}

		for(auto j:v2[ti]){

			ta.modify(j,0);

			tb.modify(j,yr[j]);

		}

		vera[ti]=ta.curver();

		verb[ti]=tb.curver();

	}

	rp(i,n)sum[i]=sum[i-1]+yr[i];

	q=in();

	ll ans=0;

	rd(_,q){

		l=in(),r=in(),x=in();

		x=(x+ans)%P;

		if(x<=M){

			ans=ta.query(vera[x],l,r)*x+tb.query(verb[x],l,r);

		}else{

			ans=sum[r]-sum[l-1];

		}

		out(ans)('\n');

	}

	return 0;

}

//Crayan_r

巴特西

CF837G - Functions On The Segments

最新文章

热门文章