自动搬运

查看原文

来自洛谷，原作者为

	Aw顿顿 直须看尽洛城花，始共春风容易别

搬运于2025-08-24 22:33:02，当前版本为作者最后更新于2021-08-15 17:12:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意清晰，不重述。

前置知识：暴力数据结构 ODT 珂朵莉树。

由于每一次修改都是对于某一个位置的后缀进行操作，不难发现这个序列会保持单调不降。那么修改会影响到的答案显然在它所属于的区间内。

这样的答案修改可以在 $\texttt{split}$ 操作中进行。实际上，当我们将一个区间分为两个不同的部分，相当于要删掉整个区间并重新加入两个单独区间。这样的思想可以同样应用在答案的维护上。

对于区间 $[l,r]$ 其长度为 $r-l+1$，因此对于答案 $s$，首先去掉 $(r-l+1)^k$。但是新加入的贡献则分两块计算，分别是：

• $(pos-l+1)^k$。
• $(r-pos)^k$。

而这个更新的初始值应该是多少呢？实际上应该是 $n^k$（一共 $n$ 个 $0$ 全部相等）。由于这一题的特殊性，一个正整数 $v$ 并不影响结果，是个冗余条件。同时 $\texttt{split}$ 不需要返回任何一个指针。

实现代码如下：

#include<bits/stdc++.h>
#define it set<node>::iterator
#define mod 20051131
#define int long long
using namespace std;
int n,q,k,s;
int ksm(int b,int p){
	int ans=1;b%=mod;
	while(p){
		if(p&1)ans=ans*b%mod;
		b=b*b%mod;p>>=1;
	}return ans;
}struct node{
    int l,r;
    mutable int v;
    node(int l,int r,int v):l(l),r(r),v(v){}
    bool operator<(const node &x)const{
		if(l!=x.l)return l<x.l;
		return r<x.r;
	}
};set<node>tr;
void modify(int l,int r,int x){
	int t1=ksm(r-l+1,k);
	int t2=ksm(x-l+1,k);
	int t3=ksm(r-x,k);
	s=((s+mod-t1+t2)%mod+t3)%mod;
}void split(int pos){
    it x=tr.lower_bound(node(pos,pos,0));
    if(x!=tr.end()&&x->l==pos)return;
    --x;int l=x->l,r=x->r,v=x->v;
    tr.erase(x);modify(l,r,pos-1);
    tr.insert(node(l,pos-1,v));
    tr.insert(node(pos,r,v));
}signed main(){
	scanf("%lld%lld%lld",&n,&q,&k);
	tr.insert(node(1,n,0));s=ksm(n,k);
	for(int i=1;i<=q;i++){
		int x,v;scanf("%lld%lld",&x,&v);
		split(x);printf("%lld\n",s);
    }return 0;
}