【题解】P7780 [AC6-M01] Gracemeria 侵攻作战

· · 题解

题意清晰，不重述。

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

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

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

对于区间 [l,r] 其长度为 r-l+1，因此对于答案 s，首先去掉 (r-l+1)^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;
}