高级数据结构学习笔记

xtx1092515503 · 2020-04-20 19:27:39 · 个人记录

这里是搞基数据结构学习笔记

本博文是关于（比较神仙的数据结构）的题目或者数据结构的（比较神仙的题目）的刷题笔记。（实际上现在已经逐渐变成了只要是一道数据结构的题目都会扔进来的博客了……）

可能会用到的数据结构：

平衡树（splay、fhq treap）

线段树（包括主席树或权值线段树等）

树状数组

STL（如std::set或者std::vector）

奇奇怪怪的科技（例如分块等等）

I.CF19D Points

树套树第一题。

思路1.线段树套线段树

因为内外的操作类似，很容易就能想到使用线段树套线段树，然后在线段树上二分来找到答案。

复杂度是O(n\log^2 n)，常数极大，因此被卡了。

代码：

#include<bits/stdc++.h>
using namespace std;
int n;
vector<pair<int,int> >vp;
struct opt{
    int tp,x,y;
}q[200100];
struct Inner_SegTree{
    vector<int>val,sum;
    Inner_SegTree(){
        val.clear(),sum.clear();
    }
    int size(){
        return val.size();
    }
    void insert(int x){
        val.push_back(x);
    }
    void construct(){
        sort(val.begin(),val.end()),val.resize(unique(val.begin(),val.end())-val.begin());
        sum.assign(val.size()<<2,0);
    }
    int ask(int x,int l,int r,int k){
        if(val[r-1]<=k||!sum[x])return 0x3f3f3f3f;
        if(r-l==1)return val[l];
        register int mid=(l+r)>>1;
        register int tmp=ask(x<<1|1,l,mid,k);
        if(tmp!=0x3f3f3f3f)return tmp;
        return ask(x+1<<1,mid,r,k); 
    }
    void add(int x,int l,int r,int P,int k){
        if(val[l]>P||val[r-1]<P)return;
        sum[x]+=k;
        if(r-l==1)return;
        register int mid=(l+r)>>1;
        add(x<<1|1,l,mid,P,k),add(x+1<<1,mid,r,P,k);
    }
};
struct Outer_SegTree{
    vector<int>val;
    vector<Inner_SegTree>inn;
    inline int size(){
        return val.size();
    }
    inline void insert_outer(int x){
        val.push_back(x);
    }
    inline void insert_inner(int x,int l,int r,int P,int Q){
        if(val[l]>P||val[r-1]<P)return;
        inn[x].insert(Q);
        if(r-l==1)return;
        int mid=(l+r)>>1;
        insert_inner(x<<1|1,l,mid,P,Q),insert_inner(x+1<<1,mid,r,P,Q);
    }
    inline void construct_outer(){
        sort(val.begin(),val.end()),val.resize(unique(val.begin(),val.end())-val.begin());
        inn.resize(val.size()<<2);
    }
    inline void construct_inner(){
        for(register auto x:vp)insert_inner(0,0,val.size(),x.first,x.second);
        for(register auto &x:inn)x.construct();
    }
    inline void add(int x,int l,int r,int P,int Q,int k){
        if(val[l]>P||val[r-1]<P)return;
        inn[x].add(0,0,inn[x].size(),Q,k);
        if(r-l==1)return;
        register int mid=(l+r)>>1;
        add(x<<1|1,l,mid,P,Q,k),add(x+1<<1,mid,r,P,Q,k);
    }
    inline pair<int,int> ask(int x,int l,int r,int P,int Q){
        register int pmt=inn[x].ask(0,0,inn[x].size(),Q);
        if(val[r-1]<=P||pmt==0x3f3f3f3f)return make_pair(0x3f3f3f3f,0x3f3f3f3f);
        if(r-l==1)return make_pair(val[l],pmt);
        register int mid=(l+r)>>1;
        register pair<int,int> tmp=ask(x<<1|1,l,mid,P,Q);
        if(tmp!=make_pair(0x3f3f3f3f,0x3f3f3f3f))return tmp;
        return ask(x+1<<1,mid,r,P,Q); 
    }
    inline void iterate(int x,int l,int r){
        printf("%d:(%d,%d):",x,l,r);
        for(register auto i:inn[x].val)printf("%d ",i);puts("");
        if(r-l==1)return;
        register int mid=(l+r)>>1;
        iterate(x<<1|1,l,mid),iterate(x+1<<1,mid,r);
    }
}seg;
inline void read(int &x){
    x=0;
    register char c=getchar();
    while(c>'9'||c<'0')c=getchar();
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
}
inline void print(int x){
    if(x<=9)putchar('0'+x);
    else print(x/10),putchar('0'+x%10);
}
int main(){
    read(n);
    for(register int i=1;i<=n;i++){
        char s[10];
        scanf("%s",s),read(q[i].x),read(q[i].y);
        if(s[0]=='a')q[i].tp=1,vp.push_back(make_pair(q[i].x,q[i].y)),seg.insert_outer(q[i].x);
        if(s[0]=='r')q[i].tp=2;
        if(s[0]=='f')q[i].tp=3;
    }
    seg.construct_outer();
//  for(auto x:seg.val)printf("%d ",x);puts("");
    seg.construct_inner();
//  seg.iterate(0,0,seg.size());
    for(register int i=1;i<=n;i++){
        if(q[i].tp==1)seg.add(0,0,seg.val.size(),q[i].x,q[i].y,1);
        if(q[i].tp==2)seg.add(0,0,seg.val.size(),q[i].x,q[i].y,-1);
        if(q[i].tp==3){
            register pair<int,int> tmp=seg.ask(0,0,seg.val.size(),q[i].x,q[i].y);
            if(tmp==make_pair(0x3f3f3f3f,0x3f3f3f3f))putchar('-'),putchar('1'),putchar('\n');
            else print(tmp.first),putchar(' '),print(tmp.second),putchar('\n');
        }
    }
    return 0;
}

思路2.线段树套set。

因为内层线段树里面要实现的操作一共只有插入、删除和求upper_bound，因此直接用std::set替代即可。

似乎线段树比set常数还要小？最终结果是set时间长一点，仍然TLE。

#include<bits/stdc++.h>
using namespace std;
int n;
vector<pair<int,int> >vp;
struct opt{
    int tp,x,y;
}q[200100];
struct Inner_Set:set<int>{
    int ask(int x){
        set<int>::iterator it=upper_bound(x);
        if(it==end())return 0x3f3f3f3f;
        return *it;
    }
};
struct Outer_SegTree{
    vector<int>val;
    vector<Inner_Set>inn;
    inline int size(){
        return val.size();
    }
    inline void insert_outer(int x){
        val.push_back(x);
    }
    inline void construct_outer(){
        sort(val.begin(),val.end()),val.resize(unique(val.begin(),val.end())-val.begin());
        inn.resize(val.size()<<2);
    }
    inline void add(int x,int l,int r,int P,int Q,int k){
        if(val[l]>P||val[r-1]<P)return;
        if(k==1)inn[x].insert(Q);
        else inn[x].erase(Q);
        if(r-l==1)return;
        register int mid=(l+r)>>1;
        add(x<<1|1,l,mid,P,Q,k),add(x+1<<1,mid,r,P,Q,k);
    }
    inline pair<int,int> ask(int x,int l,int r,int P,int Q){
        register int pmt=inn[x].ask(Q);
        if(val[r-1]<=P||pmt==0x3f3f3f3f)return make_pair(0x3f3f3f3f,0x3f3f3f3f);
        if(r-l==1)return make_pair(val[l],pmt);
        register int mid=(l+r)>>1;
        register pair<int,int> tmp=ask(x<<1|1,l,mid,P,Q);
        if(tmp!=make_pair(0x3f3f3f3f,0x3f3f3f3f))return tmp;
        return ask(x+1<<1,mid,r,P,Q); 
    }
}seg;
inline void read(int &x){
    x=0;
    register char c=getchar();
    while(c>'9'||c<'0')c=getchar();
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
}
inline void print(int x){
    if(x<=9)putchar('0'+x);
    else print(x/10),putchar('0'+x%10);
}
int main(){
    read(n);
    for(register int i=1;i<=n;i++){
        char s[10];
        scanf("%s",s),read(q[i].x),read(q[i].y);
        if(s[0]=='a')q[i].tp=1,vp.push_back(make_pair(q[i].x,q[i].y)),seg.insert_outer(q[i].x);
        if(s[0]=='r')q[i].tp=2;
        if(s[0]=='f')q[i].tp=3;
    }
    seg.construct_outer();
    for(register int i=1;i<=n;i++){
        if(q[i].tp==1)seg.add(0,0,seg.val.size(),q[i].x,q[i].y,1);
        if(q[i].tp==2)seg.add(0,0,seg.val.size(),q[i].x,q[i].y,-1);
        if(q[i].tp==3){
            register pair<int,int> tmp=seg.ask(0,0,seg.val.size(),q[i].x,q[i].y);
            if(tmp==make_pair(0x3f3f3f3f,0x3f3f3f3f))putchar('-'),putchar('1'),putchar('\n');
            else print(tmp.first),putchar(' '),print(tmp.second),putchar('\n');
        }
    }
    return 0;
}

思路3.树状数组套set。

介于这题卡常卡的丧心病狂，考虑用常数更小的树状数组维护set。

思路就是用树状数组维护y坐标，支持单点的set插入/删除以及后缀\max（关于后缀的方法，实际上只需要把正常树状数组里面+\operatorname{lowbit}和-\operatorname{lowbit}的地方互换一下即可。

复杂度O(n\log^2n)。

代码：

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
int n,val[200100],m;
set<pii>s[200100];
struct opt{
    int tp,x,y;
}q[200100];
inline void read(int &x){
    x=0;
    register char c=getchar();
    while(c>'9'||c<'0')c=getchar();
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
}
inline void print(int x){
    if(x<=9)putchar('0'+x);
    else print(x/10),putchar('0'+x%10);
}
void ins(int x,pii k){
    while(x)s[x].insert(k),x-=x&-x;
} 
void del(int x,pii k){
    while(x)s[x].erase(k),x-=x&-x;
}
pii ask(int x,pii k){
    pii res=make_pair(0x3f3f3f3f,0x3f3f3f3f);
    while(x<=m)res=min(res,*s[x].lower_bound(k)),x+=x&-x;
    return res;
}
int main(){
    read(n);
    for(register int i=1;i<=n;i++){
        char str[10];
        scanf("%s",str),read(q[i].x),read(q[i].y);
        if(str[0]=='a')q[i].tp=1;
        if(str[0]=='r')q[i].tp=2;
        if(str[0]=='f')q[i].tp=3,q[i].x++,q[i].y++;
        val[++m]=q[i].y;
    }
    sort(val+1,val+m+1),m=unique(val+1,val+m+1)-val+1;
    for(int i=1;i<=m;i++)s[i].insert(make_pair(0x3f3f3f3f,0x3f3f3f3f));
    for(register int i=1;i<=n;i++){
        if(q[i].tp==1)ins(lower_bound(val+1,val+m,q[i].y)-val,make_pair(q[i].x,q[i].y));
        if(q[i].tp==2)del(lower_bound(val+1,val+m,q[i].y)-val,make_pair(q[i].x,q[i].y));
        if(q[i].tp==3){
            register pii tmp=ask(lower_bound(val+1,val+m,q[i].y)-val,make_pair(q[i].x,q[i].y));
            if(tmp==make_pair(0x3f3f3f3f,0x3f3f3f3f))putchar('-'),putchar('1'),putchar('\n');
            else print(tmp.first),putchar(' '),print(tmp.second),putchar('\n');
        }
    }
    return 0;
}

II.Dynamic Rankings

树状数组套权值线段树。

正经不带修的方法就是主席树（即一堆权值线段树并一起）。现在带修了，那就把这些主席树拆开，拆成n棵权值线段树，然后用树状数组进行单点修改以及前缀求和，复杂度O(n\log^2n)。

代码：

#include<bits/stdc++.h>
using namespace std;
#define mid ((l+r)>>1)
int n,m,root[100100],cnt,bin[1001000],tp,lim,num[100100];
vector<int>v;
struct node{
    int lson,rson,sum;
}seg[20001000];
int newid(){
    if(!tp)return ++cnt;
    return bin[tp--];
}
void ADD(int &x,int l,int r,int P,int val){
    if(l>P||r<P)return;
    if(!x)x=newid();
    seg[x].sum+=val;
    if(l==r)return;
    ADD(seg[x].lson,l,mid,P,val),ADD(seg[x].rson,mid+1,r,P,val);
    if(!seg[x].sum)bin[++tp]=x,x=0;
}
void add(int x,int y,int z){
    while(x<=n)ADD(root[x],1,lim,y,z),x+=x&-x;
}
int Query(vector<int>&x,vector<int>&y,int l,int r,int k){
    if(l==r)return l;
    int lsum=0;
    for(auto i:x)lsum+=seg[seg[i].lson].sum;
    for(auto i:y)lsum-=seg[seg[i].lson].sum;
    if(k<=lsum){
        for(auto &i:x)i=seg[i].lson;
        for(auto &i:y)i=seg[i].lson;
        return Query(x,y,l,mid,k);
    }else{
        for(auto &i:x)i=seg[i].rson;
        for(auto &i:y)i=seg[i].rson;
        return Query(x,y,mid+1,r,k-lsum);
    }
}
int ask(int l,int r,int k){
    vector<int>x,y;
    l--;
    while(r)x.push_back(root[r]),r-=r&-r;
    while(l)y.push_back(root[l]),l-=l&-l;
    return Query(x,y,1,lim,k);
}
struct opt{
    int op,x,y,z;
}q[100100];
void iterate(int x,int l,int r){
    if(!x)return;
    iterate(seg[x].lson,l,mid),iterate(seg[x].rson,mid+1,r);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&num[i]),v.push_back(num[i]);
    for(int i=1;i<=m;i++){
        char s[10];
        scanf("%s",s);
        if(s[0]=='Q')q[i].op=1,scanf("%d%d%d",&q[i].x,&q[i].y,&q[i].z);
        else q[i].op=2,scanf("%d%d",&q[i].x,&q[i].y),v.push_back(q[i].y);
    }
    sort(v.begin(),v.end()),v.resize(unique(v.begin(),v.end())-v.begin()),lim=v.size();
//  for(auto i:v)printf("%d ",i);puts("");
    for(int i=1;i<=n;i++)add(i,num[i]=lower_bound(v.begin(),v.end(),num[i])-v.begin()+1,1);
    for(int i=1;i<=m;i++){
        if(q[i].op==1)printf("%d\n",v[ask(q[i].x,q[i].y,q[i].z)-1]);
        else add(q[i].x,num[q[i].x],-1),add(q[i].x,num[q[i].x]=lower_bound(v.begin(),v.end(),q[i].y)-v.begin()+1,1);
    }
    return 0;
}

III.CF1093E Intersection of Permutations

首先，我们如果令c[i]表示b[i]在数组a中出现的位置，

那么对于一次询问，答案就是c中下标在[l_2,r_2]间的数字中，值位于[l_1,r_1]间的数量。

思路1.树状数组套权值线段树。

很明显，这题的操作如果不带修可以用主席树完成（下标在[l_2,r_2]里面的树上进行值域查询）。带了修改，则套上树状数组完事。

代码：

#include<bits/stdc++.h>
using namespace std;
#define mid ((l+r)>>1)
int n,m,root[200100],cnt,bin[10010000],tp,num[200100],a[200100],b[200100];
struct node{
    int lson,rson,sum;
}seg[20001000];
int newid(){
    if(!tp)return ++cnt;
    return bin[tp--];
}
void ADD(int &x,int l,int r,int P,int val){
    if(l>P||r<P)return;
    if(!x)x=newid();
    seg[x].sum+=val;
    if(l!=r)ADD(seg[x].lson,l,mid,P,val),ADD(seg[x].rson,mid+1,r,P,val);
    if(!seg[x].sum)bin[++tp]=x,x=0;
}
void add(int x,int y,int z){
    while(x<=n)ADD(root[x],1,n,y,z),x+=x&-x;
}
int Query(int x,int l,int r,int L,int R){
    if(!x||l>R||r<L)return 0;
    if(L<=l&&r<=R)return seg[x].sum;
    return Query(seg[x].lson,l,mid,L,R)+Query(seg[x].rson,mid+1,r,L,R);
}
int ask(int l,int r,int L,int R){
    l--;
    int res=0;
    while(r)res+=Query(root[r],1,n,L,R),r-=r&-r;
    while(l)res-=Query(root[l],1,n,L,R),l-=l&-l;
    return res;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1,x;i<=n;i++)scanf("%d",&x),a[x]=i;
    for(int i=1,x;i<=n;i++)scanf("%d",&x),b[i]=a[x];
    for(int i=1;i<=n;i++)add(i,b[i],1);
    for(int i=1,t1,t2,t3,t4,t5;i<=m;i++){
        scanf("%d",&t1);
        if(t1==1)scanf("%d%d%d%d",&t2,&t3,&t4,&t5),printf("%d\n",ask(t4,t5,t2,t3));
        else scanf("%d%d",&t2,&t3),add(t2,b[t2],-1),add(t3,b[t3],-1),swap(b[t2],b[t3]),add(t2,b[t2],1),add(t3,b[t3],1);
    }
    return 0;
}

思路2.奇奇怪怪的分块-ver1.0

我们在数组c上分块，在每个块内排序。每次整块二分，散块直接暴力，复杂度O(n\sqrt{n}\log n)。

因为实现很糟糕，因此它T掉了。

TLE代码：

#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
const int BBB=600;
int n,m,BLK[200100],ra[200100],c[200100],d[200100],lp[1000],lim;
inline void SWAP(int x,int y){
    swap(c[x],c[y]);
    for(register int i=lp[BLK[x]];i<lp[BLK[x]+1];i++)d[i]=c[i];
    sort(d+lp[BLK[x]],d+lp[BLK[x]+1]);
    for(register int i=lp[BLK[y]];i<lp[BLK[y]+1];i++)d[i]=c[i];
    sort(d+lp[BLK[y]],d+lp[BLK[y]+1]);
}
inline int CALC(int l,int r,int L,int R){
    register int res=0;
    if(BLK[L]==BLK[R]){
        for(register int i=L;i<R;i++)res+=(c[i]>=l&&c[i]<r);
        return res;
    }
    for(register int i=L;i<lp[BLK[L]+1];i++)res+=(c[i]>=l&&c[i]<r);
    for(register int i=lp[BLK[R]];i<R;i++)res+=(c[i]>=l&&c[i]<r);
    for(register int i=BLK[L]+1;i<BLK[R];i++)res+=lower_bound(d+lp[i],d+lp[i+1],r)-lower_bound(d+lp[i],d+lp[i+1],l);
    return res; 
}
inline void read(int &x){
    x=0;
    register char c=getchar();
    while(c>'9'||c<'0')c=getchar();
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
}
inline int read(){
    register int x=0;
    register char c=getchar();
    while(c>'9'||c<'0')c=getchar();
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x;
}
inline void print(int x){
    if(x<=9)putchar('0'+x);
    else print(x/10),putchar('0'+x%10);
}
int main(){
    read(n),read(m);
    for(register int i=0;i<n;i++)ra[read()]=i,BLK[i]=i/BBB;
    for(register int i=0;i<n;i++)c[i]=d[i]=ra[read()];
    lim=BLK[n-1]+1;
    for(register int i=0;i<lim;i++)lp[i]=i*BBB;
    lp[lim]=n,BLK[n]=lim;
    for(register int i=0;i<lim;i++)sort(d+lp[i],d+lp[i+1]);
    for(register int i=1,t1,t2,t3,t4,t5;i<=m;i++){
        read(t1);
        if(t1==1)read(t2),read(t3),read(t4),read(t5),t2--,t4--,print(CALC(t2,t3,t4,t5)),putchar('\n');
        else read(t2),read(t3),t2--,t3--,SWAP(t2,t3);
    }
    return 0;
}

思路3.奇奇怪怪的分块-ver2.0

设块长为k，我们分析一下各个操作的复杂度：

整块复杂度为O(k\log\dfrac{n}{k})=O(k\log n)

散块复杂度为O(\dfrac{n}{k})

修改复杂度为O(\dfrac{n}{k}\log\dfrac{n}{k})=\dfrac{n}{k}\log n

则当k=\sqrt{n}时复杂度最优，为O(\sqrt{n}\log n)。

我们如果只考虑询问复杂度的话，这个k是可以取到\sqrt{n\log n}的。关键是修改。

有两种思路。

1. 考虑将修改也分块。将修改储存下来，每累计\sqrt{n\log n}个修改后，就暴力O(n\log n)全部推平重新排序。则每次询问时，只需要O(\sqrt{n\log n})遍历所有修改并更新答案即可。复杂度O(\sqrt{n\log n})。

2. 原本的修改，我们是\dfrac{n}{k}\log n重新排序的；发现修改只作用于一个位置；故可以直接O(k)插入排序，或者直接套上std::set让修改优化到O(\log k)。（实际上，套上set后就已经相当于一种树套树了，是分块套平衡树）

代码：

#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
const int BBB=1000;
int n,m,BLK[200100],ra[200100],c[200100],d[200100],lp[1000],lim;
vector<pair<int,int> >v;
inline int CALC(int l,int r,int L,int R){
    register int res=0;
    for(auto x:v){
        res-=(x.first>=L)&&(x.first<R)&&(c[x.first]>=l)&&(c[x.first]<r);
        res-=(x.second>=L)&&(x.second<R)&&(c[x.second]>=l)&&(c[x.second]<r);
        swap(c[x.first],c[x.second]);
        res+=(x.first>=L)&&(x.first<R)&&(c[x.first]>=l)&&(c[x.first]<r);
        res+=(x.second>=L)&&(x.second<R)&&(c[x.second]>=l)&&(c[x.second]<r);
    }
    for(int i=v.size()-1;i>=0;i--)swap(c[v[i].first],c[v[i].second]);
    if(BLK[L]==BLK[R]){
        for(register int i=L;i<R;i++)res+=(c[i]>=l&&c[i]<r);
        return res;
    }
    for(register int i=L;i<lp[BLK[L]+1];i++)res+=(c[i]>=l&&c[i]<r);
    for(register int i=lp[BLK[R]];i<R;i++)res+=(c[i]>=l&&c[i]<r);
    for(register int i=BLK[L]+1;i<BLK[R];i++)res+=lower_bound(d+lp[i],d+lp[i+1],r)-lower_bound(d+lp[i],d+lp[i+1],l);
    return res; 
}
void init(){
    for(auto x:v)swap(c[x.first],c[x.second]);
    v.clear();
    for(int i=0;i<n;i++)d[i]=c[i];
    for(int i=0;i<lim;i++)sort(d+lp[i],d+lp[i+1]);
}
inline void read(int &x){
    x=0;
    register char c=getchar();
    while(c>'9'||c<'0')c=getchar();
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
}
inline int read(){
    register int x=0;
    register char c=getchar();
    while(c>'9'||c<'0')c=getchar();
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x;
}
inline void print(int x){
    if(x<=9)putchar('0'+x);
    else print(x/10),putchar('0'+x%10);
}
int main(){
    read(n),read(m);
    for(register int i=0;i<n;i++)ra[read()]=i,BLK[i]=i/BBB;
    for(register int i=0;i<n;i++)c[i]=ra[read()];
    lim=BLK[n-1]+1;
    for(register int i=0;i<lim;i++)lp[i]=i*BBB;
    lp[lim]=n,BLK[n]=lim;
    init();
    for(register int i=1,t1,t2,t3,t4,t5;i<=m;i++){
        read(t1);
        if(t1==1)read(t2),read(t3),read(t4),read(t5),t2--,t4--,print(CALC(t2,t3,t4,t5)),putchar('\n');
        else read(t2),read(t3),t2--,t3--,v.push_back(make_pair(t2,t3));
        if(v.size()>=BBB)init();
    }
    return 0;
}

IV.【模板】二逼平衡树（树套树）

树状数组套权值线段树最好了……n\log^2n的复杂度可比n\log^3n的什么线段树套平衡树要强一百万倍！其实是我不会写

分析一下操作：

1. 二分出来最大的<k的数后直接权值线段树上查询前缀和。

2. 就是II.Dynamic Rankings。

3. 直接修改。

4. 权值线段树上二分前驱。

5. 权值线段树上二分后继。

操作全都是O(\log^2n)的。

敲出来，一遍90\%，TLE一个点，祭出快读，AC。

代码：

#include<bits/stdc++.h>
using namespace std;
#define mid ((l+r)>>1)
int n,m,cnt,bin[1001000],tp,root[50100],lim,val[50100];
struct node{
    int lson,rson,sum;
}seg[5010000];
vector<int>v;
inline void newnode(int &x){
    if(!tp)x=++cnt;
    else x=bin[tp--];
}
inline void segmod(int &x,int l,int r,int P,int val){
    if(l>P||r<P)return;
    if(!x)newnode(x);
    seg[x].sum+=val;
    if(l!=r)segmod(seg[x].lson,l,mid,P,val),segmod(seg[x].rson,mid+1,r,P,val);
    if(!seg[x].sum)bin[++tp]=x,x=0;
}
inline void finmod(int x,int P,int k){
    while(x<=n)segmod(root[x],1,lim,P,k),x+=x&-x;
}
inline void modify(int x,int y){
    y=lower_bound(v.begin(),v.end(),y)-v.begin()+1;
    finmod(x,val[x],-1);
    finmod(x,val[x]=y,1);
}
inline int segkth(vector<int>&x,vector<int>&y,int l,int r,int k){
    int lsum=0;
    if(l==r)return v[l-1];
    for(auto i:x)lsum+=seg[seg[i].lson].sum;
    for(auto i:y)lsum-=seg[seg[i].lson].sum;
    if(lsum>=k){
        for(auto &i:x)i=seg[i].lson;
        for(auto &i:y)i=seg[i].lson;
        return segkth(x,y,l,mid,k);
    }else{
        for(auto &i:x)i=seg[i].rson;
        for(auto &i:y)i=seg[i].rson;
        return segkth(x,y,mid+1,r,k-lsum);      
    }
}
inline int finkth(int l,int r,int k){
    vector<int>x,y;
    l--;
    while(l)y.push_back(root[l]),l-=l&-l;
    while(r)x.push_back(root[r]),r-=r&-r;
    return segkth(x,y,1,lim,k);
}
inline int segrak(int x,int l,int r,int L,int R){
    if(!x||l>R||r<L)return 0;
    if(L<=l&&r<=R)return seg[x].sum;
    return segrak(seg[x].lson,l,mid,L,R)+segrak(seg[x].rson,mid+1,r,L,R);
}
inline int finrak(int x,int y){
    int sum=0;
    while(x)sum+=segrak(root[x],1,lim,1,y),x-=x&-x;
    return sum;
}
inline int rak(int l,int r,int x){
    x=lower_bound(v.begin(),v.end(),x)-v.begin();
    return finrak(r,x)-finrak(l-1,x)+1;
}
inline int segpre(vector<int>&x,vector<int>&y,int l,int r,int k){
    int sum=0;
    for(auto i:x)sum+=seg[i].sum;
    for(auto i:y)sum-=seg[i].sum; 
    if(!sum||l>k)return *v.begin();
    if(l==r)return v[l-1];
    vector<int>p,q;
    p.clear(),q.clear();
    for(auto i:x)p.push_back(seg[i].rson);
    for(auto i:y)q.push_back(seg[i].rson);
    int tmp=segpre(p,q,mid+1,r,k);
    if(tmp!=*v.begin())return tmp;
    p.clear(),q.clear();
    for(auto i:x)p.push_back(seg[i].lson);
    for(auto i:y)q.push_back(seg[i].lson);
    return segpre(p,q,l,mid,k);
}
inline int finpre(int l,int r,int k){
    k=lower_bound(v.begin(),v.end(),k)-v.begin();
    vector<int>x,y;
    l--;
    while(l)y.push_back(root[l]),l-=l&-l;
    while(r)x.push_back(root[r]),r-=r&-r;
    return segpre(x,y,1,lim,k);
}
inline int segsuf(vector<int>&x,vector<int>&y,int l,int r,int k){
    int sum=0;
    for(auto i:x)sum+=seg[i].sum;
    for(auto i:y)sum-=seg[i].sum;
    if(!sum||r<k)return *v.rbegin();
    if(l==r)return v[l-1];
    vector<int>p,q;
    p.clear(),q.clear();
    for(auto i:x)p.push_back(seg[i].lson);
    for(auto i:y)q.push_back(seg[i].lson);
    int tmp=segsuf(p,q,l,mid,k);
    if(tmp!=*v.rbegin())return tmp;
    p.clear(),q.clear();
    for(auto i:x)p.push_back(seg[i].rson);
    for(auto i:y)q.push_back(seg[i].rson);
    return segsuf(p,q,mid+1,r,k);
}
inline int finsuf(int l,int r,int k){
    k=upper_bound(v.begin(),v.end(),k)-v.begin()+1;
    vector<int>x,y;
    l--;
    while(l)y.push_back(root[l]),l-=l&-l;
    while(r)x.push_back(root[r]),r-=r&-r;
    return segsuf(x,y,1,lim,k);
}
struct opt{
    int op,t1,t2,t3;
}q[50100];
inline void read(int &x){
    x=0;
    char c=getchar();
    while(c>'9'||c<'0')c=getchar();
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
}
inline void print(int x){
    if(x<0)putchar('-'),print(-x);
    else if(x<=9)putchar('0'+x);
    else print(x/10),putchar('0'+x%10);
}
int main(){
    read(n),read(m),v.push_back(-2147483647),v.push_back(2147483647);
    for(int i=1;i<=n;i++)read(val[i]),v.push_back(val[i]);
    for(int i=1;i<=m;i++){
        read(q[i].op),read(q[i].t1),read(q[i].t2);
        if(q[i].op==3)v.push_back(q[i].t2);
        else read(q[i].t3);
    }
    sort(v.begin(),v.end()),v.resize(lim=(unique(v.begin(),v.end())-v.begin()));
//  for(auto x:v)printf("%d ",x);puts("");
    for(int i=1;i<=n;i++)finmod(i,val[i]=lower_bound(v.begin(),v.end(),val[i])-v.begin()+1,1);
//  puts("IN");
    for(int i=1;i<=m;i++){
        if(q[i].op==1)print(rak(q[i].t1,q[i].t2,q[i].t3)),putchar('\n');
        if(q[i].op==2)print(finkth(q[i].t1,q[i].t2,q[i].t3)),putchar('\n');
        if(q[i].op==3)modify(q[i].t1,q[i].t2);
        if(q[i].op==4)print(finpre(q[i].t1,q[i].t2,q[i].t3)),putchar('\n');
        if(q[i].op==5)print(finsuf(q[i].t1,q[i].t2,q[i].t3)),putchar('\n');
    }
    return 0;
} 

V.【模板】三维偏序（陌上花开）

树套树比CDQ分治可爱一万倍！！！数据结构什么的最可爱了！！！

那么树套树如何进行三维偏序呢？

首先，第一维直接排序掉。

第二位用树状数组处理。

第三维套上权值线段树。

具体地说，因为我们要支持任何地方的单点修改以及前缀查询，就不得不套上树状数组。

这样，树套树便能完美替代一切CDQ能做的事。

代码：

#include<bits/stdc++.h>
using namespace std;
#define mid ((l+r)>>1)
int n,m,cnt,root[200100],res[200100];
struct obj{
    int a,b,c;
    friend bool operator <(const obj &x,const obj &y){
        if(x.a!=y.a)return x.a<y.a;
        if(x.b!=y.b)return x.b<y.b;
        return x.c<y.c;
    }
    friend bool operator ==(const obj &x,const obj &y){
        return x.a==y.a&&x.b==y.b&&x.c==y.c;
    }
}q[100100];
struct SegTree{
    int lson,rson,sum;
}seg[10010000];
void add(int &x,int l,int r,int P){
    if(l>P||r<P)return;
    if(!x)x=++cnt;
    seg[x].sum++;
    if(l==r)return;
    add(seg[x].lson,l,mid,P),add(seg[x].rson,mid+1,r,P);
}
void ADD(int x,int y){
    while(x<=m)add(root[x],1,m,y),x+=x&-x;
}
int sum(int x,int l,int r,int P){
    if(!x||l>P)return 0;
    if(r<=P)return seg[x].sum;
    return sum(seg[x].lson,l,mid,P)+sum(seg[x].rson,mid+1,r,P);
}
int SUM(int x,int y){
    int Sum=0;
    while(x)Sum+=sum(root[x],1,m,y),x-=x&-x;
    return Sum;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d%d%d",&q[i].a,&q[i].b,&q[i].c);
    sort(q+1,q+n+1);
    for(int i=1,j=1;i<=n;i=j){
        while(q[j]==q[i])ADD(q[j].b,q[j].c),j++;
        res[SUM(q[i].b,q[i].c)-1]+=j-i;
    }
    for(int i=0;i<n;i++)printf("%d\n",res[i]);
    return 0;
}

VI.[CQOI2011]动态逆序对

这题需要支持查询前缀大于某个值的数量、后缀小于某个值的数量以及在某个地方插入值。

换句话说，我们要支持在以下标为x轴，权值为y轴的二维平面上动态删点以及询问矩形和。

如果我们把删点的时间看做z轴的话，那就是典型的三维偏序。

直接树套树完成。

代码（常数贼大，勉强卡过）：

#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mid ((l+r)>>1)
int n,m,cnt,root[2][100100],a[100100],b[100100],c[100100];
ll res[100100],all;
struct node{
    int lson,rson,sum;
}seg[20010000];
void add(int &x,int l,int r,int P){
    if(l>P||r<P)return;
    if(!x)x=++cnt;
    seg[x].sum++;
    if(l==r)return;
    add(seg[x].lson,l,mid,P),add(seg[x].rson,mid+1,r,P);
}
void ADD(int x,int y){
    int tmp;
    tmp=x;
    while(tmp<=n)add(root[0][tmp],1,n,y),tmp+=tmp&-tmp;
    tmp=x;
    while(tmp>=1)add(root[1][tmp],1,n,y),tmp-=tmp&-tmp;
}
int ask(int x,int l,int r,int L,int R){
    if(!x||l>R||r<L)return 0;
    if(L<=l&&r<=R)return seg[x].sum;
    return ask(seg[x].lson,l,mid,L,R)+ask(seg[x].rson,mid+1,r,L,R);
}
ll ASK(int x,int y){
    ll s=0;
    int tmp;
    tmp=x-1;
    while(tmp>=1)s+=ask(root[0][tmp],1,n,y,n),tmp-=tmp&-tmp;
    tmp=x+1;
    while(tmp<=n)s+=ask(root[1][tmp],1,n,1,y),tmp+=tmp&-tmp;
    return s;
}
bool on[100100];
int read(){
    int x=0;
    char c=getchar();
    while(c>'9'||c<'0')c=getchar();
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x;
}
int main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++)c[a[i]=read()]=i;
    for(int i=1;i<=m;i++)on[c[b[i]=read()]]=true;
    for(int i=1;i<=n;i++)if(!on[i])all+=ASK(i,a[i]),ADD(i,a[i]);
    for(int i=m;i;i--)all+=ASK(c[b[i]],b[i]),ADD(c[b[i]],b[i]),res[i]=all;
    for(int i=1;i<=m;i++)printf("%lld\n",res[i]);
    return 0;
}

VII.[ZJOI2013]K大数查询

这题常卡的我快哭了QaQ

首先，我们仍然考虑树套树。

1. 下标树套权值树（即我们前几题的一贯做法）

我们发现，要在区间树上打上区间添加数的tag，并且用tag树的并集进行二分。

因此最终的结果就是，大区间被分割成\log n个小区间，但是每个小区间的\log n个父亲区间的tag树都是必须选的。因此总共有\log^2n个tag树在一起二分，因此总复杂度就是\log^3n的。并且写起来还贼恶心。介于这题贼卡长，我不认为这种方法有通过的可能性。

2. 权值树套下标树

现在，我们就是在权值树的某个叶节点上的下标树内，打上一个区间加的tag。当然咯，这叶节点的所有父亲的下标树，也是要打tag的。

最终的结果就是，修改就是在\log n个下标树内打区间加tag，复杂度\log^2n。

然后询问。就直接在权值树上二分，同时在下标树上查询区间和，复杂度\log^2n。

被卡长的代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,Inc,root[200100],dis[200100],tp;
struct Inner{
    int lson,rson,tag;
    ll sum;
}inn[20010000];
inline void pushdown(const register int &x,const register int &l,const register int &r){
    register int mid=(l+r)>>1,&val=inn[x].tag;
    if(!inn[x].lson)inn[x].lson=++Inc;
    if(!inn[x].rson)inn[x].rson=++Inc;
    inn[inn[x].lson].sum+=1ll*val*(mid-l+1),inn[inn[x].lson].tag+=val;
    inn[inn[x].rson].sum+=1ll*val*(r-mid),inn[inn[x].rson].tag+=val;
    val=0;
}
inline void Inner_Add(register int &x,const register int &l,const register int &r,const register int &L,const register int &R){
    if(!x)x=++Inc;
    if(L<=l&&r<=R){inn[x].sum+=r-l+1,inn[x].tag++;return;}
    if(inn[x].tag)pushdown(x,l,r);
    register int mid=(l+r)>>1;
    if(mid>=L)Inner_Add(inn[x].lson,l,mid,L,R);
    if(mid<R)Inner_Add(inn[x].rson,mid+1,r,L,R);
    inn[x].sum=inn[inn[x].lson].sum+inn[inn[x].rson].sum;
}
inline ll Inner_Ask(const register int &x,const register int &l,const register int &r,const register int &L,const register int &R){
    if(L<=l&&r<=R)return inn[x].sum;
    if(inn[x].tag)pushdown(x,l,r);
    register int mid=(l+r)>>1;
    ll res=0;
    if(mid>=L&&inn[x].lson)res+=Inner_Ask(inn[x].lson,l,mid,L,R);
    if(mid<R&&inn[x].rson)res+=Inner_Ask(inn[x].rson,mid+1,r,L,R);
    return res;
}
inline void Outer_Add(const register int &x,const register int &l,const register int &r,const register int &P,const register int &L,const register int &R){
    Inner_Add(root[x],1,n,L,R);
    if(l==r)return;
    register int mid=(l+r)>>1;
    if(mid>=P)Outer_Add(x<<1,l,mid,P,L,R);
    else Outer_Add(x<<1|1,mid+1,r,P,L,R);
}
inline int Outer_Ask(const register int &x,const register int &l,const register int &r,const register int &L,const register int &R,const register ll &k){
    if(l==r)return l;
    register ll rsum=Inner_Ask(root[x<<1|1],1,n,L,R);
    register int mid=(l+r)>>1;
    if(rsum>=k)return Outer_Ask(x<<1|1,mid+1,r,L,R,k);
    else return Outer_Ask(x<<1,l,mid,L,R,k-rsum);
}
struct Query{
    int tp,l,r;
    ll k;
}q[50100];
inline void read(register int &x){
    register char c=getchar();
    register int fl=1;
    while(c>'9'||c<'0')fl=(c=='-'?-fl:fl),c=getchar();
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
    x*=fl;
}
inline void read(register ll &x){
    register char c=getchar();
    register int fl=1;
    while(c>'9'||c<'0')fl=(c=='-'?-fl:fl),c=getchar();
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
    x*=fl;
}
inline void print(register int x){
    if(x<0)putchar('-'),print(-x);
    else if(x<=9)putchar('0'+x);
    else print(x/10),putchar('0'+x%10);
}
int main(){
    read(n),read(m);
    for(register int i=1;i<=m;i++){
        read(q[i].tp),read(q[i].l),read(q[i].r),read(q[i].k);
        if(q[i].tp==1)dis[++tp]=q[i].k;
    }
    sort(dis+1,dis+tp+1),tp=unique(dis+1,dis+tp+1)-dis-1;
    for(register int i=1;i<=m;i++){
        if(q[i].tp==1)Outer_Add(1,1,tp,lower_bound(dis+1,dis+tp+1,q[i].k)-dis,q[i].l,q[i].r);
        else print(dis[Outer_Ask(1,1,tp,q[i].l,q[i].r,q[i].k)]),putchar('\n');
    }
    return 0;
}

能用的优化就只有在下标树上的标记永久化了。

因此现学了这个东西，敲出来常数果然快了很多，勉强卡过了：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,Inc,root[200100],dis[200100],tp;
struct Inner{
    int lson,rson,tag;
    ll sum;
}inn[20010000];
inline void Inner_Add(register int &x,const register int &l,const register int &r,const register int &L,const register int &R){
    if(!x)x=++Inc;
    inn[x].sum+=max(min(R,r)-max(L,l)+1,0);
    if(L<=l&&r<=R){inn[x].tag++;return;}
    register int mid=(l+r)>>1;
    if(mid>=L)Inner_Add(inn[x].lson,l,mid,L,R);
    if(mid<R)Inner_Add(inn[x].rson,mid+1,r,L,R);
}
inline ll Inner_Ask(const register int &x,const register int &l,const register int &r,const register int &L,const register int &R,const register int add=0){
    if(!x)return 1ll*add*max(min(R,r)-max(L,l)+1,0);
    if(L<=l&&r<=R)return 1ll*add*(r-l+1)+inn[x].sum;
    register int mid=(l+r)>>1;
    register ll res=0;
    if(mid>=L)res+=Inner_Ask(inn[x].lson,l,mid,L,R,add+inn[x].tag);
    if(mid<R)res+=Inner_Ask(inn[x].rson,mid+1,r,L,R,add+inn[x].tag);
    return res;
}
inline void Outer_Add(const register int &x,const register int &l,const register int &r,const register int &P,const register int &L,const register int &R){
    Inner_Add(root[x],1,n,L,R);
    if(l==r)return;
    register int mid=(l+r)>>1;
    if(mid>=P)Outer_Add(x<<1,l,mid,P,L,R);
    else Outer_Add(x<<1|1,mid+1,r,P,L,R);
}
inline int Outer_Ask(const register int &x,const register int &l,const register int &r,const register int &L,const register int &R,const register ll &k){
    if(l==r)return l;
    register ll rsum=Inner_Ask(root[x<<1|1],1,n,L,R);
    register int mid=(l+r)>>1;
    if(rsum>=k)return Outer_Ask(x<<1|1,mid+1,r,L,R,k);
    else return Outer_Ask(x<<1,l,mid,L,R,k-rsum);
}
struct Query{
    int tp,l,r;
    ll k;
}q[50100];
inline void read(register int &x){
    register char c=getchar();
    register int fl=1;
    while(c>'9'||c<'0')fl=(c=='-'?-fl:fl),c=getchar();
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
    x*=fl;
}
inline void read(register ll &x){
    register char c=getchar();
    register int fl=1;
    while(c>'9'||c<'0')fl=(c=='-'?-fl:fl),c=getchar();
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
    x*=fl;
}
inline void print(register int x){
    if(x<0)putchar('-'),print(-x);
    else if(x<=9)putchar('0'+x);
    else print(x/10),putchar('0'+x%10);
}
int main(){
    read(n),read(m);
    for(register int i=1;i<=m;i++){
        read(q[i].tp),read(q[i].l),read(q[i].r),read(q[i].k);
        if(q[i].tp==1)dis[++tp]=q[i].k;
    }
    sort(dis+1,dis+tp+1),tp=unique(dis+1,dis+tp+1)-dis-1;
    for(register int i=1;i<=m;i++){
        if(q[i].tp==1)Outer_Add(1,1,tp,lower_bound(dis+1,dis+tp+1,q[i].k)-dis,q[i].l,q[i].r);
        else print(dis[Outer_Ask(1,1,tp,q[i].l,q[i].r,q[i].k)]),putchar('\n');
    }
    return 0;
}

VIII.CF785E Anton and Permutation

我们看一下交换以后，哪些逆序对会受到影响。

设交换了位置(x,y)，它们原本的值是val_x,val_y。不妨设x<y。

对于一个位置i<x，x,y在交换后仍然都排在它后面，不受影响；

对于一个位置i>y，x,y在交换后仍然都排在它前面，不受影响；

对于一个位置i\in(x,y)，这时就会产生影响了。

对于一个val_i>\max(val_x,val_y)或val_i<\min(val_x,val_y)，交换后前后的大小关系不变，不受影响。

则受影响的只有i\in(i,j),val_i\in(val_x,val_y)，这时要么新出现两个逆序对，要么消失两个逆序对。

树套树维护一下，复杂度O(n\log^2n)。

代码：

#include<bits/stdc++.h>
using namespace std;
#define mid ((l+r)>>1)
typedef long long ll;
int n,m,root[200100],bin[1001000],tp,cnt,val[200100];
ll res;
struct node{
    int lson,rson,sum;
}seg[20010000];
void newnode(int &x){
    if(!tp)x=++cnt;
    else x=bin[tp--];
}
void add(int &x,int l,int r,int P,int val){
    if(l>P||r<P)return;
    if(!x)newnode(x);
    seg[x].sum+=val;
    if(l!=r)add(seg[x].lson,l,mid,P,val),add(seg[x].rson,mid+1,r,P,val);
    if(!seg[x].sum)bin[++tp]=x,x=0;
}
void ADD(int x,int y,int k){
    while(x<=n)add(root[x],1,n,y,k),x+=x&-x;
}
int ask(int x,int l,int r,int L,int R){
    if(!x||l>R||r<L)return 0;
    if(L<=l&&r<=R)return seg[x].sum;
    return ask(seg[x].lson,l,mid,L,R)+ask(seg[x].rson,mid+1,r,L,R);
}
int ASK(int x,int L,int R){
    ll ret=0;
    while(x)ret+=ask(root[x],1,n,L,R),x-=x&-x;
    return ret;
}
ll SWAP(int x,int y){
    if(x==y)return res;
    if(x>y)swap(x,y);
    ADD(x,val[x],-1),ADD(y,val[y],-1);
    if(val[x]<val[y])res++,res+=(ASK(y-1,val[x],val[y])-ASK(x,val[x],val[y]))<<1;
    else res--,res-=(ASK(y-1,val[y],val[x])-ASK(x,val[y],val[x]))<<1;
    swap(val[x],val[y]);
    ADD(x,val[x],1),ADD(y,val[y],1);
    return res;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)ADD(i,val[i]=i,1);
    for(int i=1,x,y;i<=m;i++)scanf("%d%d",&x,&y),printf("%lld\n",SWAP(x,y));
    return 0;
}

IX.[TJOI2017]不勤劳的图书管理员

我要举报……出题人语文明显不太好……

首先，这题就是上一题的带权版。

然后，这题带了权后和上一题就不太一样了。

当你交换位置x,y的书后，（默认x<y）

位置在x前或在y后的书不受影响；

位置在x,y之间，且val_z\in(val_x,val_y)的书z，效果和之前一样。只不过，这次还要算上x和y的贡献。

位置在x,y之间，且val_z\in(1,val_x)的书z，虽然它自己的贡献没变，但是它对x,y的贡献却改变了；具体的说，改变了val_y-val_x。

位置在x,y之间，且val_z\in(val_y,n)的书z，类似的，改变了val_x-val_y。

然后因为出题人语文不好，我整整在错误的方向上努力了一晚上……

代码（比第一篇暴力的题解还要慢……）：

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
#define mid ((l+r)>>1)
#define pii pair<int,int>
pii operator +(const pii &x,const pii &y){
    return make_pair((x.first+y.first)%mod,(x.second+y.second)%mod);
}
void operator +=(pii &x,const pii &y){
    (x.first+=y.first)%=mod,(x.second+=y.second)%=mod;
}
pii operator -(const pii &x,const pii &y){
    return make_pair((x.first-y.first+mod)%mod,(x.second-y.second+mod)%mod);
}
typedef long long ll;
int n,m,root[50100],cnt,val[50100],bok[50100],pos[50100],res;
struct node{
    int lson,rson;
    pii sum;
}seg[10010000];
void add(int &x,int l,int r,int P,int val){
    if(l>P||r<P)return;
    if(!x)x=++cnt;
    (seg[x].sum.first+=(val+mod)%mod)%=mod;
    (seg[x].sum.second+=(val>0?1:-1)+mod)%=mod;
    if(l!=r)add(seg[x].lson,l,mid,P,val),add(seg[x].rson,mid+1,r,P,val);
}
void ADD(int x,int y,int k){
    while(x<=n)add(root[x],1,n,y,k),x+=x&-x;
}
pii ask(int x,int l,int r,int L,int R){
    if(!x||l>R||r<L)return make_pair(0,0);
    if(L<=l&&r<=R)return seg[x].sum;
    return ask(seg[x].lson,l,mid,L,R)+ask(seg[x].rson,mid+1,r,L,R);
}
pii ASK(int x,int L,int R){
    pii ret=make_pair(0,0);
    while(x)ret+=ask(root[x],1,n,L,R),x-=x&-x;
    return ret;
}
int SWAP(int x,int y){
    if(x==y)return res;
    if(x>y)swap(x,y);
    ADD(x,bok[x],-val[x]),ADD(y,bok[y],-val[y]);
    if(bok[x]<bok[y]){
        pii tmp;
        tmp=ASK(y-1,bok[x],bok[y])-ASK(x,bok[x],bok[y]);
        (res+=(tmp.first<<1)%mod)%=mod;
        (res+=1ll*(tmp.second+1)*(val[x]+val[y])%mod)%=mod;

        tmp=ASK(y-1,1,bok[x])-ASK(x,1,bok[x]);
        (res+=1ll*(val[y]-val[x]+mod)%mod*tmp.second%mod)%=mod;

        tmp=ASK(y-1,bok[y],n)-ASK(x,bok[y],n);
        (res+=1ll*(val[x]-val[y]+mod)%mod*tmp.second%mod)%=mod;
    }
    else{
        pii tmp;
        tmp=ASK(y-1,bok[y],bok[x])-ASK(x,bok[y],bok[x]);
        (res+=mod-(tmp.first<<1)%mod)%=mod;
        (res+=mod-1ll*(tmp.second+1)*(val[x]+val[y])%mod)%=mod;

        tmp=ASK(y-1,1,bok[y])-ASK(x,1,bok[y]);
        (res+=1ll*(val[y]-val[x]+mod)%mod*tmp.second%mod)%=mod;

        tmp=ASK(y-1,bok[x],n)-ASK(x,bok[x],n);
        (res+=1ll*(val[x]-val[y]+mod)%mod*tmp.second%mod)%=mod;
    }
    swap(bok[x],bok[y]),swap(val[x],val[y]);
    ADD(x,bok[x],val[x]),ADD(y,bok[y],val[y]);
    return res;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&bok[i],&val[i]);
        pii tmp=ASK(i,bok[i],n);
        (res+=tmp.first)%=mod;
        (res+=1ll*tmp.second*val[i]%mod)%=mod;
        ADD(i,bok[i],val[i]);
    }
    for(int i=1,x,y;i<=m;i++)scanf("%d%d",&x,&y),printf("%d\n",SWAP(x,y));
    return 0;
}

X.CF650D Zip-line

我们考虑在修改一个位置后，新的LIS可能有哪些。

1. 就是原序列中的LIS。

设原序列LIS长度为len。

此时有两种可能：

A.被修改的位置在LIS中不是不可替代的（换句话说，有至少一条LIS不经过此位置）。此时，长度就是len。

B.被修改的位置在LIS中不可替代（换句话说，所有LIS都经过此位置）。此时，长度是len-1。

至于如何判断是不是不可替代的吗……可以记录以当前位置开头和结尾的LIS数量，然后与总LIS数量比较。如果开头结尾的LIS数量之积等于总LIS数量，则该位置是不可替代的。

因为LIS数量非常非常大，因此模上一个大数哈希一下即可。

2. 不是原序列中的LIS。

则我们要找到所有在它前面且比它小的位置中前缀长度的最大值，以及所有在它后面且比它大的位置中后缀长度的最大值，然后拼在一起完成。

考虑用主席树维护即可。

但是！！！这题卡空间，两棵主席树就是40倍空间，跑不过去。

被卡的主席树代码：

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
#define mid ((l+r)>>1)
#define pii pair<int,int>
#define mp make_pair
#define ff first
#define ss second
int n,root1[400100],root2[400100],a[400100],m,lim,cnt;
pii mx;
pii f[400100],g[400100];
vector<int>v;
struct SegTree{
    int lson,rson;
    pii sum;
}seg[16001000];
pii operator +=(pii&x,const pii&y){
    if(x.ff==y.ff)(x.ss+=y.ss),x.ss%=mod;
    else if(x.ff<y.ff)x=y;
}
pii operator +(const pii&x,const pii&y){
    if(x.ff==y.ff)return make_pair(x.ff,(x.ss+y.ss)%mod);
    return max(x,y);
}
void modify(int &x,int y,int l,int r,int P,pii val){
    if(l>P||r<P)return;
    x=++cnt;
    seg[x]=seg[y],seg[x].sum+=val;
    if(l!=r)modify(seg[x].lson,seg[y].lson,l,mid,P,val),modify(seg[x].rson,seg[y].rson,mid+1,r,P,val);
}
pii query(int x,int l,int r,int L,int R){
    if(l>R||r<L)return mp(0,0);
    if(L<=l&&r<=R)return seg[x].sum;
    return query(seg[x].lson,l,mid,L,R)+query(seg[x].rson,mid+1,r,L,R);
}
void build(int &x,int l,int r){
    x=++cnt;
    if(l!=r)build(seg[x].lson,l,mid),build(seg[x].rson,mid+1,r);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),v.push_back(a[i]);
    sort(v.begin(),v.end()),v.resize(unique(v.begin(),v.end())-v.begin()),lim=v.size();
    for(int i=1;i<=n;i++)a[i]=lower_bound(v.begin(),v.end(),a[i])-v.begin()+1;
    build(root1[0],1,lim);
    for(int i=1;i<=n;i++){
        f[i]=query(root1[i-1],1,lim,1,a[i]-1),f[i].first++;
        if(f[i].first==1)f[i].second++;
        modify(root1[i],root1[i-1],1,lim,a[i],f[i]),mx+=f[i];
    }
    build(root2[n+1],1,lim);
    for(int i=n;i>=1;i--){
        g[i]=query(root2[i+1],1,lim,a[i]+1,lim),g[i].first++;
        if(g[i].first==1)g[i].second++;
        modify(root2[i],root2[i+1],1,lim,a[i],g[i]);
    }
    for(int i=1,x,y,res;i<=m;i++){
        scanf("%d%d",&x,&y);
        if(f[x].first+g[x].first-1==mx.first&&1ll*f[x].second*g[x].second%mod==mx.second)res=mx.first-1;
        else res=mx.first;
        res=max(res,query(root1[x-1],1,lim,1,lower_bound(v.begin(),v.end(),y)-v.begin()).first+1+query(root2[x+1],1,lim,upper_bound(v.begin(),v.end(),y)-v.begin()+1,lim).first);
        printf("%d\n",res);
    }
    return 0;
}

主席树是暴力的思想，但是是在线的。如果我们把它离线下来，就可以在建主席树时直接回答当前位置的询问。而主席树实际上是线段树的前缀和，故直接用线段树维护即可。只需要4倍空间。

代码：

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
#define lson x<<1
#define rson x<<1|1
#define mid ((l+r)>>1)
#define pii pair<int,int>
#define mp make_pair
#define ff first
#define ss second
int n,a[400100],m,lim,res[400100];
pii mx;
pii f[400100],g[400100],seg[1600100];
vector<int>v;
vector<pii>q[400100];
pii operator +=(pii&x,const pii&y){
    if(x.ff==y.ff)(x.ss+=y.ss),x.ss%=mod;
    else if(x.ff<y.ff)x=y;
}
pii operator +(const pii&x,const pii&y){
    if(x.ff==y.ff)return make_pair(x.ff,(x.ss+y.ss)%mod);
    return max(x,y);
}
void modify(int x,int l,int r,int P,pii val){
    if(l>P||r<P)return;
    seg[x]+=val;
    if(l!=r)modify(lson,l,mid,P,val),modify(rson,mid+1,r,P,val);
}
pii query(int x,int l,int r,int L,int R){
    if(l>R||r<L)return mp(0,0);
    if(L<=l&&r<=R)return seg[x];
    return query(lson,l,mid,L,R)+query(rson,mid+1,r,L,R);
}
void build(int x,int l,int r){
    seg[x]=mp(0,0);
    if(l!=r)build(lson,l,mid),build(rson,mid+1,r);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),v.push_back(a[i]);
    sort(v.begin(),v.end()),v.resize(unique(v.begin(),v.end())-v.begin()),lim=v.size();
    for(int i=1;i<=n;i++)a[i]=lower_bound(v.begin(),v.end(),a[i])-v.begin()+1;
    for(int i=1,x,y;i<=m;i++)scanf("%d%d",&x,&y),q[x].push_back(mp(y,i));
    build(1,1,lim);
    for(int i=1;i<=n;i++){
        f[i]=query(1,1,lim,1,a[i]-1),f[i].first++;
        if(f[i].first==1)f[i].second++;
        for(auto j:q[i])res[j.second]=query(1,1,lim,1,lower_bound(v.begin(),v.end(),j.first)-v.begin()).first+1;
        modify(1,1,lim,a[i],f[i]),mx+=f[i];
    }
    build(1,1,lim);
    for(int i=n;i>=1;i--){
        g[i]=query(1,1,lim,a[i]+1,lim),g[i].first++;
        if(g[i].first==1)g[i].second++;
        int fal=(f[i].first+g[i].first-1==mx.first&&1ll*f[i].second*g[i].second%mod==mx.second?mx.first-1:mx.first);
        for(auto j:q[i])res[j.second]+=query(1,1,lim,upper_bound(v.begin(),v.end(),j.first)-v.begin()+1,lim).first,res[j.second]=max(res[j.second],fal);
        modify(1,1,lim,a[i],g[i]);
    }
    for(int i=1;i<=m;i++)printf("%d\n",res[i]);
    return 0;
}

XI.CF85D Sum of Medians

这题做法有无数种，其中最暴力的一种就是用vector爆算用5棵fhq treap直接处理。比线段树要好想的多。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,root[5],cnt,bin[100100],tp;
struct treap{
    int lson,rson,val,rd,sz;
    ll sum;
}t[100100];
int newnode(int val){
    int x=(tp?bin[tp--]:++cnt);
    t[x].lson=t[x].rson=0,t[x].sum=t[x].val=val,t[x].rd=rand()*rand(),t[x].sz=1;
    return x;
}
void pushup(int x){
    t[x].sum=t[x].val,t[x].sz=1;
    if(t[x].lson)t[x].sum+=t[t[x].lson].sum,t[x].sz+=t[t[x].lson].sz; 
    if(t[x].rson)t[x].sum+=t[t[x].rson].sum,t[x].sz+=t[t[x].rson].sz;
}
void split(int x,int k,int &u,int &v){
    if(!x){u=v=0;return;}
    if(t[x].val<=k)u=x,split(t[x].rson,k,t[x].rson,v);
    else v=x,split(t[x].lson,k,u,t[x].lson);
    pushup(x);
}
int merge(int x,int y){
    if(!x||!y)return x+y;
    if(t[x].rd<t[y].rd){t[x].rson=merge(t[x].rson,y),pushup(x);return x;}
    else{t[y].lson=merge(x,t[y].lson),pushup(y);return y;}
}
int main(){
    srand(19260817);
    scanf("%d",&n);
    for(int i=1,x;i<=n;i++){
        char s[10];
        scanf("%s",s);
        if(s[0]=='a'){
            scanf("%d",&x);
            int u[5],v[5],sz=1;
            for(int i=0;i<5;i++)split(root[i],x,u[i],v[i]),sz+=t[u[i]].sz,root[i]=u[i];
            x=newnode(x);
            root[sz%5]=merge(root[sz%5],x);
            for(int i=0;i<5;i++)root[i]=merge(root[i],v[(i+4)%5]);
        }
        if(s[0]=='d'){
            scanf("%d",&x);
            int u[5],v[5],w[5];
            for(int i=0;i<5;i++)split(root[i],x,u[i],v[i]),split(u[i],x-1,root[i],w[i]);
            for(int i=0;i<5;i++)root[i]=merge(root[i],v[(i+1)%5]);
        }
        if(s[0]=='s')printf("%lld\n",t[root[3]].sum);
    }
    return 0;
}

XII.初级版：[NOI2003]文本编辑器；进阶版：[AHOI2006]文本编辑器

两道题操作基本一致，唯一的区别就是进阶版多了一个翻转操作，因此干脆合在一起讲。

可以使用splay或fhq treap通过。个人认为fhq treap更加直观。

光标的位置，我们用一个值tar表示。

Move/Next/Prev：直接修改tar的值即可。

Insert：笛卡尔树O(n)建树并插入。

Delete：split出有效区间然后删掉即可。可以采取空间回收，这是很好的习惯，因为你不知道会不会RE/MLE。

Get：直接输出split后右半部最靠左那个地方的字符即可。

Rotate：fhq treap上打区间翻转的tag即可。

[NOI2003]文本编辑器代码：

#include<bits/stdc++.h>
using namespace std;
int n,rt,cnt,bin[5001000],tp,tar,stk[5001000],bd;
char s[5001000];
void getstring(int len){
    char c=getchar();
    for(int i=0;i<len;i++){
        while(c>126||c<32)c=getchar();
        s[i]=c,c=getchar();
    }
}
int read(){
    int x=0;
    char c=getchar();
    while(c>'9'||c<'0')c=getchar();
    while(c>='0'&&c<='9')x=x*10+c-48,c=getchar();
    return x;
}
struct treap{
    int lson,rson,rd,sz;
    char ch;
}t[5001000];
int newnode(char ch){
    int x=tp?bin[tp--]:++cnt;
    t[x].ch=ch,t[x].lson=t[x].rson=0,t[x].sz=1,t[x].rd=rand()*rand();
    return x;
}
void pushup(int x){
    t[x].sz=1;
    if(t[x].lson)t[x].sz+=t[t[x].lson].sz;
    if(t[x].rson)t[x].sz+=t[t[x].rson].sz;
}
void split(int x,int k,int &u,int &v){
    if(!x){u=v=0;return;}
    if(t[t[x].lson].sz>=k)v=x,split(t[x].lson,k,u,t[x].lson);
    else u=x,split(t[x].rson,k-t[t[x].lson].sz-1,t[x].rson,v);
    pushup(x);
}
int merge(int x,int y){
    if(!x||!y)return x+y;
    if(t[x].rd>t[y].rd){t[x].rson=merge(t[x].rson,y),pushup(x);return x;}
    else{t[y].lson=merge(x,t[y].lson),pushup(y);return y;}
}
void iterate(int x){
    if(!x)return;
    iterate(t[x].lson);
    putchar(t[x].ch);
    iterate(t[x].rson);
}
void oldnode(int x){
    if(!x)return;
    oldnode(t[x].lson),oldnode(t[x].rson),bin[++tp]=x;
}
int build(int len){
    int las;
    for(int i=0;i<len;i++){
        int x=newnode(s[i]);
        las=0;
        while(bd&&t[stk[bd]].rd<t[x].rd)pushup(stk[bd]),las=stk[bd--];
        if(bd)t[stk[bd]].rson=x;
        t[stk[++bd]=x].lson=las;
    }
    while(bd)pushup(stk[bd--]);
    return stk[1];
} 
void Move(){tar=read();}
void Insert(){
    int len=read();
    getstring(len);
    int a,b;
    split(rt,tar,a,b);
    rt=merge(merge(a,build(len)),b);
}
void Delete(){
    int len=read();
    int a,b,c;
    split(rt,tar,a,b);
    split(b,len,b,c);
    oldnode(b);
    rt=merge(a,c);
}
void Get(){
    int len=read();
    int a,b,c;
    split(rt,tar,a,b);
    split(b,len,b,c);
    iterate(b);putchar('\n'); 
    rt=merge(merge(a,b),c);
}
void Prev(){tar--;}
void Next(){tar++;}
int main(){
    n=read();
    while(n--){
        scanf("%s",s);
        if(s[0]=='I')Insert();
        else if(s[0]=='M')Move();
        else if(s[0]=='D')Delete();
        else if(s[0]=='G')Get();
        else if(s[0]=='P')Prev();
        else if(s[0]=='N')Next();
    }
    return 0;
}

[AHOI2006]文本编辑器代码：

#include<bits/stdc++.h>
using namespace std;
int n,stk[5001000],tp,bin[5001000],bd,cnt,tar,rt;
char s[5001000];
void getstring(int len){
    for(int i=0;i<len;i++)s[i]=getchar(); 
}
int read(){
    int x=0;
    char c=getchar();
    while(c>'9'||c<'0')c=getchar();
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x;
}
struct treap{
    int lson,rson,rd,sz;
    char ch;
    bool rev;
}t[5001000];
int newnode(char ch){
    int x=tp?bin[tp--]:++cnt;
    t[x].lson=t[x].rson=0,t[x].rd=rand()*rand(),t[x].sz=1,t[x].ch=ch,t[x].rev=false;
    return x;
}
void oldnode(int x){
    if(!x)return;
    oldnode(t[x].lson),oldnode(t[x].rson),bin[++tp]=x;
}
void pushup(int x){
    t[x].sz=1;
    if(t[x].lson)t[x].sz+=t[t[x].lson].sz;
    if(t[x].rson)t[x].sz+=t[t[x].rson].sz;
}
void REV(int x){
    swap(t[x].lson,t[x].rson),t[x].rev^=1;
}
void pushdown(int x){
    if(!t[x].rev)return;
    REV(t[x].lson),REV(t[x].rson),t[x].rev=false;
}
int merge(int x,int y){
    if(!x||!y)return x+y;
    if(t[x].rd>t[y].rd){pushdown(x),t[x].rson=merge(t[x].rson,y),pushup(x);return x;}
    else{pushdown(y),t[y].lson=merge(x,t[y].lson),pushup(y);return y;}
} 
void split(int x,int k,int &u,int &v){
    if(!x){u=v=0;return;}
    pushdown(x);
    if(t[t[x].lson].sz>=k)v=x,split(t[x].lson,k,u,t[x].lson);
    else u=x,split(t[x].rson,k-t[t[x].lson].sz-1,t[x].rson,v);
    pushup(x);
}
void Insert(){
    int len=read();
    getstring(len);
    for(int i=0;i<len;i++){
        int x=newnode(s[i]),las=0;
        while(bd&&t[stk[bd]].rd<t[x].rd)pushup(stk[bd]),las=stk[bd--];
        if(bd)t[stk[bd]].rson=x;
        t[stk[++bd]=x].lson=las;
    }
    while(bd)pushup(stk[bd--]);
    int a,b;
    split(rt,tar,a,b);
    rt=merge(merge(a,stk[1]),b);
}
void Delete(){
    int len=read();
    int a,b,c;
    split(rt,tar,a,b);
    split(b,len,b,c);
    rt=merge(a,c),oldnode(b);
}
void Rotate(){
    int len=read();
    int a,b,c;
    split(rt,tar,a,b);
    split(b,len,b,c);
    REV(b),rt=merge(merge(a,b),c);
}
void Move(){tar=read();}
void Next(){tar++;}
void Prev(){tar--;}
void leftmost(int x){
    pushdown(x);
    if(!t[x].lson){
        putchar(t[x].ch);
        if(t[x].ch!='\n')putchar('\n'); 
    }else leftmost(t[x].lson);
}
/*
void iterate(int x){
    if(!x)return;
    pushdown(x);
    iterate(t[x].lson);
    putchar(t[x].ch);
    iterate(t[x].rson);
}
*/
void Get(){
    int a,b;
    split(rt,tar,a,b);
    leftmost(b);
    rt=merge(a,b);
}
int main(){
    n=read();
    while(n--){
        scanf("%s",s);
        if(s[0]=='M')Move();
        else if(s[0]=='I')Insert();
        else if(s[0]=='D')Delete();
        else if(s[0]=='R')Rotate();
        else if(s[0]=='G')Get();
        else if(s[0]=='P')Prev();
        else if(s[0]=='N')Next();
//      iterate(rt),putchar('\n');
    }
    return 0;
}

XIII.CF226E Noble Knight's Path

这题分为在线和离线两种做法然而我只会在线

在线的思路很简单，即先树剖，然后建出主席树。主席树一维维护的是时间，每一棵主席树内部维护的是树剖剖出来的结果。

然后对于每一次询问：

首先先从两边跳链，找到LCA，并找出两点路径间没有被“亵渎”的城堡数。如果这一数量小于询问，直接输出-1。

否则，先从x往上一直跳到LCA，如果这一段中未被“亵渎”的城堡数已经足够了，就直接输出；否则，从y点向上跳，类似地找未被亵渎的城堡。

那怎么输出呢？这就要在线段树上二分了。当然，反正总复杂度已经是\log^2了，你要嫌麻烦直接写\log^2的二分套线段树也没有问题，毕竟线段树上二分写起来确实挺恶心的。不过这里写的还是线段树上二分。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=100100;
int n,m,des[N];
//------------------------Chain Decompotision---------------
int dfn[N],rev[N],fa[N],dep[N],son[N],top[N],sz[N],head[N],cnt,tot;
struct node{
    int to,next;
}edge[200100];
void ae(int u,int v){
    edge[cnt].next=head[u],edge[cnt].to=v,head[u]=cnt++;
    edge[cnt].next=head[v],edge[cnt].to=u,head[v]=cnt++;
}
void dfs1(int x,int Fa){
    fa[x]=Fa,dep[x]=dep[Fa]+1,sz[x]=1;
    for(int i=head[x],y;i!=-1;i=edge[i].next){
        if((y=edge[i].to)==fa[x])continue;
        dfs1(y,x),sz[x]+=sz[y];
        if(sz[son[x]]<sz[y])son[x]=y;
    }
}
void dfs2(int x){
    if(son[x])top[son[x]]=top[x],dfn[son[x]]=++tot,rev[tot]=son[x],dfs2(son[x]);
    for(int i=head[x],y;i!=-1;i=edge[i].next){
        y=edge[i].to;
        if(y==fa[x]||y==son[x])continue;
        top[y]=y,dfn[y]=++tot,rev[tot]=y,dfs2(y);
    }
}
//--------------Persistent Segment Tree--------------------
#define mid ((l+r)>>1)
int rt[N],newid;
struct SegTree{
    int lson,rson,sum;
}seg[20001000];
void build(int &x,int l,int r){
    x=++newid;
    if(l!=r)build(seg[x].lson,l,mid),build(seg[x].rson,mid+1,r);
}
void modify(int &x,int y,int l,int r,int P){
    if(l>P||r<P)return;
    seg[x=++newid]=seg[y],seg[x].sum++;
    if(l!=r)modify(seg[x].lson,seg[y].lson,l,mid,P),modify(seg[x].rson,seg[y].rson,mid+1,r,P);
}
int asksize(int x,int l,int r,int L,int R){
    if(l>R||r<L)return 0;
    if(L<=l&&r<=R)return seg[x].sum;
    return asksize(seg[x].lson,l,mid,L,R)+asksize(seg[x].rson,mid+1,r,L,R);
}
int rangeask(int x,int y,int l,int r,int k){
    if(l==r)return rev[l];
    if((mid-l+1)-(seg[seg[y].lson].sum-seg[seg[x].lson].sum)>=k)return rangeask(seg[x].lson,seg[y].lson,l,mid,k);
    else return rangeask(seg[x].rson,seg[y].rson,mid+1,r,k-((mid-l+1)-(seg[seg[y].lson].sum-seg[seg[x].lson].sum)));
}
int askkth(int x,int y,int l,int r,int L,int R,int &k,bool &findans){
    if(l>R||r<L)return 0;
    if(L<=l&&r<=R){
        if((r-l+1)-(seg[y].sum-seg[x].sum)>=k){findans=true;return rangeask(x,y,l,r,k);}
        else{k-=(r-l+1)-(seg[y].sum-seg[x].sum);return 0;};
    }
    int tmp=askkth(seg[x].lson,seg[y].lson,l,mid,L,R,k,findans);
    if(findans)return tmp;
    return askkth(seg[x].rson,seg[y].rson,mid+1,r,L,R,k,findans);
}
#define AS(A,B,L,R) (R-L+1)-(asksize(rt[B],1,n,L,R)-asksize(rt[A],1,n,L,R))
int main(){
    scanf("%d",&n),memset(head,-1,sizeof(head));
    for(int i=1,x;i<=n;i++){
        scanf("%d",&x);
        if(x)ae(x,i);
    }
    dfs1(1,0),top[1]=dfn[1]=rev[1]=tot=1,dfs2(1);
    build(rt[0],1,n);
    scanf("%d",&m);
    for(int i=1,a,b,c,d,tp,res;i<=m;i++){
        scanf("%d",&tp);
        if(tp==1)scanf("%d",&a),des[a]=i,modify(rt[i],rt[i-1],1,n,dfn[a]);
        else{
            rt[i]=rt[i-1],res=0;
            scanf("%d%d%d%d",&a,&b,&c,&d);
            if(des[a]<=d)c++;
            int x=a,y=b,len=0;
            while(top[x]!=top[y]){
                if(dep[top[x]]<dep[top[y]])swap(x,y);
                len+=AS(d,i,dfn[top[x]],dfn[x]),x=fa[top[x]];
            }
            if(dep[x]>dep[y])swap(x,y);
            len+=AS(d,i,dfn[x],dfn[y]);
            len-=(des[b]<=d);
            if(len<c){puts("-1");continue;}
//---------------------getpath&LCA-------------------------         
            int LCA=x;
            x=a;
            bool getans=false;
            while(dep[x]>=dep[LCA]){
                int anc=(dep[top[x]]<dep[LCA]?LCA:top[x]);
                int tmp=AS(d,i,dfn[anc],dfn[x]);
                if(c>tmp)c-=tmp,len-=tmp;
                else{c=tmp-c+1;res=askkth(rt[d],rt[i],1,n,dfn[anc],dfn[x],c,getans);break;}
                x=fa[top[x]];
            }
            if(getans){printf("%d\n",res);continue;}
//--------------------check A-----------------------------
            y=b;
            c=len-c+1;
            if(des[b]<=d)c++;
            while(true){
                int dfntop=dfn[top[y]];
                if(dep[top[y]]<=dep[LCA])dfntop=dfn[LCA]+1;
                int tmp=AS(d,i,dfntop,dfn[y]);
                if(c>tmp)c-=tmp;
                else{c=tmp-c+1;res=askkth(rt[d],rt[i],1,n,dfntop,dfn[y],c,getans);break;}
                y=fa[top[y]];
            }
            printf("%d\n",res);
        }
    }
    return 0;
} 

XIV.SP1557 GSS2 - Can you answer these queries II

我认为这是GSS题目中难度最大的一道，不接受反驳。

这题中出现多次的只给算一次，应该咋办呢？

我们回忆起这种情况的经典老题：[SDOI2009]HH的项链。正解是将询问离线后按照右端点递增排序，然后出现多次的，就只计算从最后一次出现的位置到当前这个位置这段区间的贡献。

于是本题也可以类似地做。

我们仍然按照右端点递增顺序枚举，设当前右端点为i。我们维护对于每个位置j，子段[j,i]的和，设为s_j。则当i从i-1移动到i时，区间[las_{a_i}+1,i]中的所有s_j都会被增加a_i。于是我们可以用线段树维护s数组。

则我们发现，对于一次询问[l,r]，我们只需要求出当i=r时，区间[l,r]中的历史最大值即可。

我们考虑对于线段树上每个节点维护这样一些东西：

当我们修改一个位置的值的时候：

当我们pushdown的时候：

• 子节点的MX与mx_{son}+TAG_{fa}取\max；

• 子节点的TAG与tag_{son}+TAG_{fa}取\max；

• 之后，子节点的mx与tag正常地更新。

• 然后，父节点的tag与TAG清空。

我们可以把这俩玩意轻松地二合一：

void ADD(int x,int y,int z=0){z=max(z,y),seg[x].MX=max(seg[x].MX,seg[x].mx+z),seg[x].TAG=max(seg[x].TAG,seg[x].tag+z),seg[x].mx+=y,seg[x].tag+=y;}

询问的时候，就直接返回对应区间的MX即可。

时间复杂度O(n\log n)。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,a[100100],res[100100];
map<int,int>mp;
struct Query{
    int l,r,id;
    friend bool operator <(const Query &x,const Query &y){
        return x.r<y.r;
    }
}q[100100];
#define lson x<<1
#define rson x<<1|1
#define mid ((l+r)>>1) 
struct SegTree{
    ll mx,tag,MX,TAG;//mx:the current maximum in the section; MX:the history maximum in the section; tag:the lazy tag for mx; TAG:the lazy tag for MX
}seg[400100];
void ADD(int x,int y,int z=0){z=max(z,y),seg[x].MX=max(seg[x].MX,seg[x].mx+z),seg[x].TAG=max(seg[x].TAG,seg[x].tag+z),seg[x].mx+=y,seg[x].tag+=y;}
#define pushdown(x) ADD(lson,seg[x].tag,seg[x].TAG),ADD(rson,seg[x].tag,seg[x].TAG),seg[x].tag=seg[x].TAG=0
#define pushup(x) seg[x].mx=max(seg[lson].mx,seg[rson].mx),seg[x].MX=max(seg[lson].MX,seg[rson].MX)
void modify(int x,int l,int r,int L,int R,int val){
    if(l>R||r<L)return;
    if(L<=l&&r<=R){ADD(x,val);return;}
    pushdown(x),modify(lson,l,mid,L,R,val),modify(rson,mid+1,r,L,R,val),pushup(x);
}
int query(int x,int l,int r,int L,int R){
    if(l>R||r<L)return 0;
    if(L<=l&&r<=R)return seg[x].MX;
    pushdown(x);
    return max(query(lson,l,mid,L,R),query(rson,mid+1,r,L,R));
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    scanf("%d",&m);
    for(int i=1;i<=m;i++)scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;
    sort(q+1,q+m+1);
    for(int i=1,j=1;i<=n;i++){
        modify(1,1,n,mp[a[i]]+1,i,a[i]),mp[a[i]]=i;
        while(j<=m&&q[j].r<=i)res[q[j].id]=query(1,1,n,q[j].l,q[j].r),j++;
    }
    for(int i=1;i<=m;i++)printf("%d\n",res[i]);
    return 0;
}

XV.CF319E Ping-Pong

好题。

首先，离线下来离散化显然是不用说的。

然后观察这里“可以移动”的定义，发现明显可以类比图论中的连边。发现边只有有向边（两区间包含）和无向边（两区间相交）两种，又因为我们只管连通性，所以无向边可以直接使用并查集维护。而包含关系又具有可传递性，故我们最终会发现必定存在一条路径使得最多经过一条有向边（经过多条有向边的路径可以被合并）。于是我们如果使用并查集维护的话，则只需要判断所有互相可达的小区间合并后，询问的两个区间是否相同或者后者包含前者即可。

然后就是这题的精髓所在了——

我们将每个区间在线段树中拆成\log n个区间，使用vector存在节点上。则对于线段树中的某个叶子节点，它的所有父亲节点上的区间中，包含了所有包含当前叶节点的区间。

于是我们在插入一个区间后，它左右两端所在的节点的所有祖先节点上的区间都与它有交；而因为题目保证插入的区间长度递增，所以这必定连的都是无向边，故我们直接使用并查集合并即可。合并之后，在每个节点的vector内，只需保留当前区间即可。

在合并完之后，就直接拆区间即可。判断就依靠我们上文提到的性质判断。

时间复杂度O\Big(n\log n\alpha(n)\Big)。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,cnt;
struct oper{
    int tp,l,r;
}q[100100];
vector<int>v[800100],dis;
int L[100100],R[100100],dsu[100100];
int find(int x){return dsu[x]==x?x:dsu[x]=find(dsu[x]);}
#define lson x<<1
#define rson x<<1|1
#define mid ((l+r)>>1)
void merge(int x,int l,int r,int P,int id){
    if(l>P||r<P)return;
    if(!v[x].empty()){
        for(auto ip:v[x])ip=find(ip),dsu[ip]=id,L[id]=min(L[id],L[ip]),R[id]=max(R[id],R[ip]);
        v[x].clear(),v[x].push_back(id);
    }
    if(l!=r)merge(lson,l,mid,P,id),merge(rson,mid+1,r,P,id);
}
void assign(int x,int l,int r,int id){
    if(r<=L[id]||l>=R[id])return;
    if(L[id]<l&&r<R[id]){v[x].push_back(id);return;}
    assign(lson,l,mid,id),assign(rson,mid+1,r,id);
}
int main(){
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&q[i].tp,&q[i].l,&q[i].r);
        if(q[i].tp==1)dis.push_back(q[i].l),dis.push_back(q[i].r);
    }
    sort(dis.begin(),dis.end()),dis.resize(n=unique(dis.begin(),dis.end())-dis.begin());
    for(int i=1;i<=m;i++){
        if(q[i].tp==1){
            cnt++;
            dsu[cnt]=cnt,q[i].l=lower_bound(dis.begin(),dis.end(),q[i].l)-dis.begin()+1,q[i].r=lower_bound(dis.begin(),dis.end(),q[i].r)-dis.begin()+1;
            L[cnt]=q[i].l,R[cnt]=q[i].r;
            merge(1,1,n,q[i].l,cnt),merge(1,1,n,q[i].r,cnt);
            assign(1,1,n,cnt);
        }else{
            int x=q[i].l,y=q[i].r;
            x=find(x),y=find(y);
            puts(x==y||(L[y]<L[x]&&L[x]<R[y])||(L[y]<R[x]&&R[x]<R[y])?"YES":"NO");
        }
    }
    return 0;
} 

XVI.CF360B Levko and Array

明显可以二分答案为x。二分之后，我们考虑DP验证。

我们设f_i表示a_i强制保留时，最多可以保留多少个数。则我们显然有转移方程

考虑到转移的限制：

绝对值可被拆开，得到

考虑继续拆开，得到

明显此时已经是一个三维偏序问题，直接使用树套树/CDQ分治，即可以n\log^3n通过本题。

考虑某个加强版，此时若有n\leq 2\times10^5，如何对敌？

考虑(j-i)x\leq a_i-a_j\leq(i-j)x的限制，它实际上已经包含了j<i的限制（因为当j>i时两个不等式显然不可能都成立）；故我们直接以这两个做二维偏序即可。时间复杂度O(n\log^2n)。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,a[200100],t[200100],lim;
void add(int x,int y){while(x<=lim)t[x]=max(t[x],y),x+=x&-x;}
int ask(int x){int ret=0;while(x)ret=max(ret,t[x]),x-=x&-x;return ret;}
pair<ll,ll>p[200100];
vector<ll>v;
bool che(int ip){
    v.clear(),memset(t,0,sizeof(t));
    for(int i=1;i<=n;i++)p[i]=make_pair(1ll*ip*i-a[i],1ll*ip*i+a[i]),v.push_back(p[i].second);
    sort(v.begin(),v.end()),v.resize(lim=unique(v.begin(),v.end())-v.begin());
    for(int i=1;i<=n;i++)p[i].second=lower_bound(v.begin(),v.end(),p[i].second)-v.begin()+1;
    sort(p+1,p+n+1);
    int mx=0;
    for(int i=1,tmp;i<=n;i++)tmp=ask(p[i].second)+1,mx=max(mx,tmp),add(p[i].second,tmp);
    return mx+m>=n;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    int l=0,r=2e9;
    while(l<r){
        int mid=(0ll+l+r)>>1;
        if(che(mid))r=mid;
        else l=mid+1;
    }
    printf("%d\n",r);
    return 0;
}

XVII.CF1413F Roads and Ramen

首先，注意到本题等价于求路径上所有边权的异或和为0的路径长度的最大值。

然后，我们要猜/证明出一个结论，即任意一条极长合法路径，其必有一个端点是直径端点。

证明：

我们设有一条直径(S,T)。我们再设col_i表示从i节点到根节点（不妨设为1号节点）上所有边权的异或和。

1. col_S=col_T

   此时显然有(S,T)合法，又有(S,T)是直径，故(S,T)即为答案。

2. col_S\neq col_T

   假设当前我们有一条合法路径(s,t)；则显然，必有s,t的颜色同S,T中某一个点的颜色相等，假设是S。则(s,S),(t,S)两条路径中较长的一条的长度肯定大于等于(s,t)的长度，这是直径的性质。

于是我们就直接找到直径(S,T)，对二者各维护一棵线段树，查询所有到它距离为偶数的点中深度最大值即可。

时间复杂度O(n\log n)。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,head[500100],cnt;
struct node{
    int to,next;
    bool tp;
}edge[1001000];
struct SegTree{
    int dfn[500100],sz[500100],rev[500100],dep[500100],tot;
    bool ini[500100];
    int mx[2000100][2];
    bool tag[2001000];
    #define lson x<<1
    #define rson x<<1|1
    #define mid ((l+r)>>1)
    #define REV(x) tag[x]^=1,swap(mx[x][0],mx[x][1])
    void pushdown(int x){if(tag[x])REV(lson),REV(rson),tag[x]=false;}
    void pushup(int x){mx[x][0]=max(mx[lson][0],mx[rson][0]),mx[x][1]=max(mx[lson][1],mx[rson][1]);}
    void dfs(int x,int fa){
        dfn[x]=++tot,sz[x]=1,rev[tot]=x;
        for(int i=head[x];i!=-1;i=edge[i].next)if(edge[i].to!=fa)dep[edge[i].to]=dep[x]+1,ini[edge[i].to]=ini[x]^edge[i].tp,dfs(edge[i].to,x),sz[x]+=sz[edge[i].to];
    }
    void build(int x,int l,int r){
        if(l==r){mx[x][ini[rev[l]]]=dep[rev[l]];return;}
        build(lson,l,mid),build(rson,mid+1,r),pushup(x);
    }
    void modify(int x,int l,int r,int L,int R){
        if(l>R||r<L)return;
        if(L<=l&&r<=R){REV(x);return;}
        pushdown(x),modify(lson,l,mid,L,R),modify(rson,mid+1,r,L,R),pushup(x);
    }
}seg[2];
void ae(int u,int v,bool w){
    edge[cnt].next=head[u],edge[cnt].to=v,edge[cnt].tp=w,head[u]=cnt++;
    edge[cnt].next=head[v],edge[cnt].to=u,edge[cnt].tp=w,head[v]=cnt++;
}
pair<int,int>dfs(int x,int fa){
    pair<int,int>ret=make_pair(-1,x);
    for(int i=head[x];i!=-1;i=edge[i].next)if(edge[i].to!=fa)ret=max(ret,dfs(edge[i].to,x));
    ret.first++;
    return ret;
}
int main(){
    scanf("%d",&n),memset(head,-1,sizeof(head));
    for(int i=1,x,y,z;i<n;i++)scanf("%d%d%d",&x,&y,&z),ae(x,y,z);
    int S=dfs(1,0).second,T=dfs(S,0).second;
    seg[0].dfs(S,0),seg[1].dfs(T,0);
    seg[0].build(1,1,n),seg[1].build(1,1,n);
    scanf("%d",&m);
    for(int i=1,x;i<=m;i++){
        scanf("%d",&x),x--;
        int u=edge[x<<1].to,v=edge[x<<1|1].to;
        if(seg[0].dep[u]<seg[0].dep[v])swap(u,v);
        seg[0].modify(1,1,n,seg[0].dfn[u],seg[0].dfn[u]+seg[0].sz[u]-1);
        if(seg[1].dep[u]<seg[1].dep[v])swap(u,v);
        seg[1].modify(1,1,n,seg[1].dfn[u],seg[1].dfn[u]+seg[1].sz[u]-1);
        printf("%d\n",max(seg[0].mx[1][0],seg[1].mx[1][0]));
    }
    return 0;
} 

XVIII.CF679E Bear and Bad Powers of 42

一个显然的想法是，观察到可能的值域（10^{14}）内不会有很多（准确地说，一共11个）42的整数次幂。于是我们考虑每次暴力修改，则每个数最多被处理11次，复杂度显然是可以承受的。

于是我们现在问题就转变为判断一个区间中是否存在42的整数次幂。

我们对于每个数，维护这个数到下一个42的次幂的距离，并在区间上维护这一距离的\min。在区间加的时候，代表区间加的tag增加，同时代表区间\min的tag减少。

假如区间\min的tag在减少后为0了，就直接返回找到了；否则，如果其大于0，返回没找到；否则，即其小于0，无法判断有没有找到，需要继续往子区间内遍历。

假如遍历到一个位置，发现这个位置的区间修改的tag不为0（这可能意味着这段区间刚刚被进行了一次区间修改，或是访问到了叶节点——叶节点的区间修改tag（即它自己的值）显然是不为0的），那就可以直接由这个tag推出区间中的\min（毕竟整个区间的值都是相等的），再返回这个\min是否为0即可。

这也意味着我们的pushdown函数要比较细心：假设当前区间修改tag不为0，显然下传时，应该把儿子的tag全都覆盖掉——区间修改tag赋成下传的tag，区间加的tag赋成0；同时，区间\min的值也要下传，这就避免了在儿子处再算一遍的局面。

假设当前区间加tag不为0（显然，此时区间修改tag肯定为0），下传时注意判断儿子的区间修改tag是否为0，为0则加到区间加tag上，否则直接加到区间修改tag上；同时，在修改后，记得同时修改区间\min。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
const int lim=11;
ll pov[20]={1,42,1764,74088,3111696,130691232,5489031744ll,230539333248ll,9682651996416ll,406671383849472ll,17080198121677824ll};
#define lson x<<1
#define rson x<<1|1
#define mid ((l+r)>>1)
struct SegTree{
    ll tagmodi,tagadd,mn;
}seg[400100];
void ADD(int x,ll y){if(seg[x].tagmodi)seg[x].tagmodi+=y;else seg[x].tagadd+=y;seg[x].mn-=y;}
void REFRESH(int x){seg[x].mn=*lower_bound(pov,pov+lim,seg[x].tagmodi)-seg[x].tagmodi;}
void MODI(int x,ll y){seg[x].tagmodi=y,seg[x].tagadd=0,REFRESH(x);}
void pushdown(int x){
    if(seg[x].tagmodi){
        seg[lson].tagmodi=seg[rson].tagmodi=seg[x].tagmodi;
        seg[lson].mn=seg[rson].mn=seg[x].mn;
        seg[lson].tagadd=seg[rson].tagadd=0;
        seg[x].tagmodi=0;
    }
    if(seg[x].tagadd)ADD(lson,seg[x].tagadd),ADD(rson,seg[x].tagadd),seg[x].tagadd=0;
}
void pushup(int x){seg[x].mn=min(seg[lson].mn,seg[rson].mn);}
void build(int x,int l,int r){
    if(l==r){scanf("%lld",&seg[x].tagmodi),REFRESH(x);return;}
    build(lson,l,mid),build(rson,mid+1,r),pushup(x);
}
void setval(int x,int l,int r,int L,int R,int val){
    if(l>R||r<L)return;
    if(L<=l&&r<=R){MODI(x,val);return;}
    pushdown(x),setval(lson,l,mid,L,R,val),setval(rson,mid+1,r,L,R,val),pushup(x);
}
bool find(int x,int l,int r){
    if(seg[x].mn>=0)return seg[x].mn==0;
    if(seg[x].tagmodi){REFRESH(x);return seg[x].mn==0;}
    pushdown(x);
    bool ret=find(lson,l,mid)|find(rson,mid+1,r);
    pushup(x);
    return ret;
}
bool add(int x,int l,int r,int L,int R,int val){
    if(l>R||r<L)return false;
    if(L<=l&&r<=R){
        ADD(x,val);
        return find(x,l,r);
    }
    pushdown(x);
    bool ret=add(lson,l,mid,L,R,val)|add(rson,mid+1,r,L,R,val);
    pushup(x);
    return ret;
}
ll query(int x,int l,int r,int P){
    if(l==r)return seg[x].tagmodi;
    pushdown(x);
    ll ret=(P<=mid?query(lson,l,mid,P):query(rson,mid+1,r,P));
    pushup(x);
    return ret;
}
//void iterate(int x,int l,int r){if(l==r)printf("(%lld:%lld)",seg[x].tagmodi,seg[x].mn);else pushdown(x),iterate(lson,l,mid),iterate(rson,mid+1,r),pushup(x);}
int main(){
    scanf("%d%d",&n,&m);
    build(1,1,n);
    for(int i=1,a,b,c,d;i<=m;i++){
        scanf("%d%d",&a,&b);
        if(a==1)printf("%lld\n",query(1,1,n,b));
        else{
            scanf("%d%d",&c,&d);
            if(a==2)setval(1,1,n,b,c,d);
            else while(add(1,1,n,b,c,d));
        }
//      iterate(1,1,n),puts("");
    }
    return 0;
} 

XIX.「JOI 2013 Final」バブルソート 冒泡排序

首先，有一个常识性结论，就是冒泡排序的次数等于逆序对数。所以本题等价于交换两个数使得减少的逆序对数最多。

于是我们翻出VIII.CF785E Anton and Permutation中给出的结论——当i<j且a_i>a_j时，交换一对(i,j)，减少的逆序对数就等于将所有P_i=(i,a_i)映射到平面上后，以P_i为左上角、P_j为右下角的矩形中点的个数\times2，再加上其本身的1对逆序对。当然，出现在边界上的点要特判掉（这些点只能贡献1次）。

稍微想想就可以发现，最优的(i,j)，P_i一定不在某个P_k的右下方，P_j一定不在某个P_k的左上方。换言之，P_i只出现在a_i的前缀最大值的位置，P_j只出现在a_j的后缀最小值的位置。

我们考虑对于某个点k，它可以对哪些(i,j)产生贡献——明显，只有在其左上方的P_i和右下方的P_j，可以从它收到贡献。而画出图来就能发现，所有合法的i，在前缀最大值中是一段区间[i_l,i_r]；所有合法的j，也是一段区间[j_l,j_r]。

于是，我们发现它实际上被转成了一个二维矩形覆盖问题，其中一维是i，另一位是j。于是直接扫描线维护过去，求覆盖最大值即可。同时注意特判边界，以及不存在这样的(i,j)对的情形（即原序列本身已是一个递增/不降序列，递增时答案恒为1，不降时答案恒为0）。

代码：

#include<bits/stdc++.h>
using namespace std;
#define emp emplace_back
typedef long long ll;
int n,m,a[100100],pre[100100],PRE,suf[100100],SUF,t[100100];
ll res;
void add(int x){while(x)t[x]++,x-=x&-x;}
void sum(int x){for(x++;x<=m;x+=x&-x)res-=t[x];}
void cheinc(){
    bool ok=true;
    for(int i=2;i<=n;i++)ok&=(a[i]>a[i-1]);
    if(ok){puts("1");exit(0);}
    ok=true;
    for(int i=2;i<=n;i++)ok&=(a[i]>=a[i-1]);
    if(ok){puts("0");exit(0);}
}
struct Data{
    int l,r,d;
    Data(int L,int R,int D){l=L,r=R,d=D;}
};
vector<Data>v[100100];
vector<int>u;
struct SegTree{
    int tag,mx;
}seg[400100];
#define lson x<<1
#define rson x<<1|1
#define mid ((l+r)>>1)
#define ADD(x,y) seg[x].tag+=y,seg[x].mx+=y
#define pushdown ADD(lson,seg[x].tag),ADD(rson,seg[x].tag),seg[x].tag=0
#define pushup seg[x].mx=max(seg[lson].mx,seg[rson].mx)
void modify(int x,int l,int r,int L,int R,int D){
    if(l>R||r<L)return;
    if(L<=l&&r<=R)ADD(x,D);
    else pushdown,modify(lson,l,mid,L,R,D),modify(rson,mid+1,r,L,R,D),pushup;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),u.push_back(a[i]);
    sort(u.begin(),u.end()),u.resize(m=unique(u.begin(),u.end())-u.begin());
    for(int i=1;i<=n;i++)a[i]=lower_bound(u.begin(),u.end(),a[i])-u.begin()+1;
//  for(int i=1;i<=n;i++)printf("%d ",a[i]);puts("");
    cheinc();
    for(int i=1;i<=n;i++)if(!PRE||a[i]>a[pre[PRE]])pre[++PRE]=i;
    for(int i=n;i>=1;i--)if(!SUF||a[i]<a[suf[SUF]])suf[++SUF]=i;
    reverse(suf+1,suf+SUF+1);
//  for(int i=1;i<=PRE;i++)printf("%d ",pre[i]);puts("");
//  for(int i=1;i<=SUF;i++)printf("%d ",suf[i]);puts("");
    for(int i=1,j=1,k=1;i<=n;i++){
        while(j<=PRE&&i>pre[j])j++;
        while(k<=SUF&&i>suf[k])k++;
        int J=upper_bound(pre+1,pre+PRE+1,i,[](int x,int y){return a[x]<a[y];})-pre;
        int K=lower_bound(suf+1,suf+SUF+1,i,[](int x,int y){return a[x]<a[y];})-suf-1;
        v[J].emp(k,K,2),v[j].emp(k,K,-2);
        if(J&&a[pre[J-1]]==a[i])v[J-1].emp(k,K,1),v[J].emp(k,K,-1);
        if(K<=SUF&&a[suf[K+1]]==a[i])v[J].emp(K+1,K+1,1),v[j].emp(K+1,K+1,-1);
    }
    for(int i=1;i<=PRE;i++){
        for(auto j:v[i])modify(1,1,SUF,j.l,j.r,j.d);
        res=max(res,1ll*seg[1].mx);
    }
//  printf("%d\n",res);
    for(int i=1;i<=n;i++)sum(a[i]),add(a[i]);
    printf("%lld\n",-1-res);
    return 0;
}

XX.[APIO2018] New Home 新家

题解

XXI.[APIO2015]八邻旁之桥

首先先忽略所有在同侧的人，考虑异侧的人。

则明显，如果我们只在p位置修一座桥，则一个从某侧的x到另一侧的y的人，其一共要走的距离就是

（忽略了桥长，因为桥长可以被统一计算）

于是我们发现，此时x和y是独立的。于是问题就转成了数轴上有很多点，要求一个点 p 到所有点的距离和最小。

通过逐步调整法，我们可以发现p即为所有点的中位数。（因为点的数量是偶数，所以会有两个中位数，此时选择任何一个都是可以的）

进一步拆开绝对值符号之后，会发现是(\text{更大的一半数之和})-(\text{更小的一半数之和})。

现在有两座桥了。我们会发现，假如我们对所有人按照x+y排序，则一定是前一半的人走左侧的桥，后一半人走右侧的桥。这可以通过画出图来证明：两端都在左侧桥左方的人，或是都在右侧桥右方的人，显然走相应的桥最优；两端各在两侧桥两边的人，显然走任何一座桥都是可以的；唯独两端在两侧桥之间的人，画出图来，会发现走离其更近的桥更优，而比较就是按x+y比较的。

于是我们现在就可以枚举这个断点，两边就分别转成了一座桥的问题。于是我们现在就要对于每个前缀和后缀，求出其中(\text{更大的一半数之和})-(\text{更小的一半数之和})，并将两边拼在一起。

如何求出呢？

平衡树

那就太可怕了。直接使用两个堆即可，其中一个是大根堆，维护前一半数；一个是小根堆，维护后一半数。当加入一个人时，先把其x和y全部插入大根堆，然后再平衡两个堆的大小即可。假如发现平衡过后，大根堆的顶大于小根堆的顶，就交换堆顶元素即可。

时间复杂度O(n\log n)。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,r;
pair<int,int>p[100100];
vector<int>v[2];
char s[4];
ll all,mn=0x3f3f3f3f3f3f3f3f,pre[100100],suf[100100],PRE,SUF;
priority_queue<int>P,Q;//P:greater heap for smaller part; Q:smaller heap for greater part
int main(){
    scanf("%d%d",&m,&r);
    for(int i=1,x,y;i<=r;i++){
        scanf("%s%d",s,&x);
        scanf("%s%d",s+1,&y);
        if(s[0]==s[1])all+=abs(x-y);
        else p[++n]=make_pair(x,y);
    }
    all+=n;
    sort(p+1,p+n+1,[](pair<int,int>u,pair<int,int>v){return u.first+u.second<v.first+v.second;});
    while(!P.empty())P.pop();while(!Q.empty())Q.pop();PRE=SUF=0;
    for(int i=1;i<=n;i++){
        PRE+=p[i].first,PRE+=p[i].second;
        P.push(p[i].first),P.push(p[i].second);
        while(P.size()!=Q.size())PRE-=P.top(),SUF+=P.top(),Q.push(-P.top()),P.pop();
        while(P.top()>-Q.top()){
            int x=P.top(),y=-Q.top();
            PRE-=x,PRE+=y;
            SUF+=x,SUF-=y;
            P.pop(),Q.pop();
            P.push(y),Q.push(-x);
        }
        pre[i]=SUF-PRE;
    }
    while(!P.empty())P.pop();while(!Q.empty())Q.pop();PRE=SUF=0;
    for(int i=n;i>=1;i--){
        PRE+=p[i].first,PRE+=p[i].second;
        P.push(p[i].first),P.push(p[i].second);
        while(P.size()!=Q.size())PRE-=P.top(),SUF+=P.top(),Q.push(-P.top()),P.pop();
        while(P.top()>-Q.top()){
            int x=P.top(),y=-Q.top();
            PRE-=x,PRE+=y;
            SUF+=x,SUF-=y;
            P.pop(),Q.pop();
            P.push(y),Q.push(-x);
        }
        suf[i]=SUF-PRE;     
    }
    if(m==1)mn=min(pre[n],suf[1]);
    else for(int i=0;i<=n;i++)mn=min(mn,pre[i]+suf[i+1]);
    printf("%lld\n",all+mn);
    return 0;
}

XXII.CF477E Dreamoon and Notepad

题解

XXIII.[JOI 2020 Final] 火事

题解

XXIV.[Code+#1]Yazid 的新生舞会

关于众数，我们通常是对于每个数求出它作为众数的区间数。

考虑某个数 x。我们可以发现，如果令 a_i=x 的所有位置有 b_i=1，其余位置有 b_i=-1，则如果某个区间 [l,r] 关于 b 的区间和 >0 的话，则有 x 是 [l,r] 的绝对众数。

考虑区间和可以被拆成前缀和之差。于是我们考虑求出 b 的前缀和 s 数组。则，对于位置 i，我们需要找出有多少个 j，满足 j<i\land s_j<s_i。

这明显是二维数点问题，常规做法是线段树。但是，我们不能对所有颜色全部从头到尾做一遍二维数点，不然复杂度就是 O(n^2\log n) 的。考虑 s_i 数组有何性质。

稍加观察可以发现，s 数组在大部分位置都是有 s_i=s_{i-1}-1 的，只有在 a_i=x 处才会出现例外；于是我们就可以考虑相邻的两个 a_j=a_i=x。它实际在线段树上的贡献，是 [s_j,s_i) 区间 +1，可以直接完成。

然后考虑一个单独的 a_i，我们要做的是在线段树上求前缀和；现在既然是 [j,i) 的区间了，那么我们就对 [s_j,s_i) 中的所有东西都求前缀和。实际上就是对线段树上每个位置乘上了一个系数，直接在线段树上同时维护系数即可。

时间复杂度 O(n\log n)。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,a[500100];
vector<int>v[500100];
ll res;
#define lson x<<1
#define rson x<<1|1
#define mid ((l+r)>=0?(l+r)>>1:(l+r-1)>>1)
struct Segtree{
    int tag,sum;
    ll mus;
}seg[4001000];
void ADD(int x,int l,int r,int y=1){seg[x].tag+=y,seg[x].sum+=(r-l+1)*y,seg[x].mus+=1ll*((n-l)+(n-r))*(r-l+1)*y/2;}
void pushdown(int x,int l,int r){ADD(lson,l,mid,seg[x].tag),ADD(rson,mid+1,r,seg[x].tag),seg[x].tag=0;}
void pushup(int x){seg[x].sum=seg[lson].sum+seg[rson].sum,seg[x].mus=seg[lson].mus+seg[rson].mus;}
void reset(int x,int l,int r){
    seg[x].tag=seg[x].sum=seg[x].mus=0;
    if(l==r)return;
    if(seg[lson].sum)reset(lson,l,mid);
    if(seg[rson].sum)reset(rson,mid+1,r);
}
void modify(int x,int l,int r,int L,int R){
    if(l>R||r<L)return;
    if(L<=l&&r<=R)ADD(x,l,r);
    else pushdown(x,l,r),modify(lson,l,mid,L,R),modify(rson,mid+1,r,L,R),pushup(x);
}
ll querytri(int x,int l,int r,int L,int R){
    if(l>R||r<L)return 0;
    if(L<=l&&r<=R)return seg[x].mus-1ll*seg[x].sum*(n-R-1);
    pushdown(x,l,r);
    return querytri(lson,l,mid,L,R)+querytri(rson,mid+1,r,L,R); 
}
ll querypla(int x,int l,int r,int L,int R){
    if(l>=L)return 0;
    if(r<L)return 1ll*seg[x].sum*(R-L+1);
    pushdown(x,l,r);
    return querypla(lson,l,mid,L,R)+querypla(rson,mid+1,r,L,R);
}
int main(){
    scanf("%d%d",&n,&a[0]);
    for(int i=0;i<n;i++)v[i].push_back(0);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),v[a[i]].push_back(i);
    for(int i=0;i<n;i++)v[i].push_back(n+1);
    for(int i=0;i<n;i++){
        if(v[i].size()==2)continue;
        int las=0;
        for(int j=1;j+1<v[i].size();j++){
//          printf("ADD:[%d,%d]\n",las-(v[i][j]-v[i][j-1]-1),las);
            modify(1,-n,n,las-(v[i][j]-v[i][j-1]-1),las);
            las-=(v[i][j]-v[i][j-1]-1)-1;
            res+=querytri(1,-n,n,las-(v[i][j+1]-v[i][j]),las-1)+querypla(1,-n,n,las-(v[i][j+1]-v[i][j]),las-1);
//          printf("SUM:[%d,%d]:%lld\n",las-(v[i][j+1]-v[i][j]),las-1,query(1,-n,n,las-(v[i][j+1]-v[i][j]),las-1));
        }
        reset(1,-n,n);
    }
    printf("%lld\n",res);
    return 0;
}

XXV.CF702F T-Shirts

一句没有输出的调试语句忘删了，然后浪费了半小时debug\kk……

首先观察到我们可以将所有物品按照quality为第一关键字递减排序，然后再关于price为第二关键字排序，这样所有人购买的东西就都必定是按照其一个子序列的顺序购买的。

于是把询问离线下来，然后就转成了对于所有 \geq c 的询问，将其值减去 c 的套路问题。

然后这就是某道原题了。因为该原题以前是做过的，这里不再赘述（直接上平衡树暴力维护即可）

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,rt;
pair<int,int>p[200100],q[200100];
struct Treap{
    int ch[2],rd,val,tot,tagv,tagt;
}t[200100];
#define lson t[x].ch[0]
#define rson t[x].ch[1]
void SUB(int x,int y){t[x].val-=y,t[x].tagv+=y;}
void ADD(int x,int y=1){t[x].tot+=y,t[x].tagt+=y;}
void pushdown(int x){
    if(lson)SUB(lson,t[x].tagv),ADD(lson,t[x].tagt);
    if(rson)SUB(rson,t[x].tagv),ADD(rson,t[x].tagt);
    t[x].tagt=t[x].tagv=0;
}
int merge(int x,int y){
    if(!x||!y)return x+y;
    if(t[x].rd>t[y].rd){pushdown(x),t[x].ch[1]=merge(t[x].ch[1],y);return x;}
    else{pushdown(y),t[y].ch[0]=merge(x,t[y].ch[0]);return y;}
}
void split(int x,int k,int &u,int &v){
    if(!x){u=v=0;return;}
    pushdown(x);
    if(t[x].val<k)u=x,split(rson,k,rson,v);
    else v=x,split(lson,k,u,lson);
}
void reset(int &RT,int x){
    if(!x)return;
    pushdown(x);
    int a,b;
    split(RT,t[x].val,a,b);
    reset(a,lson),reset(b,rson);
    lson=rson=0;
    RT=merge(merge(a,x),b);
}
void func(int k){
    int a,b,c;
    split(rt,k,a,b);
    if(b)ADD(b),SUB(b,k);
    split(b,2*k,b,c);
    reset(a,b);
    rt=merge(a,c);
}
void iterate(int x){
    if(!x)return;
    pushdown(x);
    iterate(lson),iterate(rson);
}
int stk[200100],tp;
int read(){
    int x=0;
    char c=getchar();
    while(c>'9'||c<'0')c=getchar();
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x;
}
void print(int x){if(x<=9)putchar('0'+x);else print(x/10),putchar('0'+x%10);}
int main(){
    m=read();
    for(int i=1;i<=m;i++)p[i].second=read(),p[i].first=-read();sort(p+1,p+m+1);
    n=read();for(int i=1;i<=n;i++)q[i].first=t[i].val=read(),q[i].second=i,t[i].rd=rand()*rand();
    sort(q+1,q+n+1);
    for(int i=1;i<=n;i++){
        int x=q[i].second;
        while(tp&&t[stk[tp]].rd<t[x].rd)t[x].ch[0]=stk[tp--];
        if(tp)t[stk[tp]].ch[1]=x;
        stk[++tp]=x;
    }rt=stk[1];
    for(int i=1;i<=m;i++)func(p[i].second);
    iterate(rt);for(int i=1;i<=n;i++)printf("%d",t[i].tot),putchar(' ');
    return 0;
}

XXVI.CF1458C Latin Square

实际上此题使用的数据结构不很高级，甚至可以说很不高级——因为全程只用了数组。但是本题的思想绝对是非常高级的。

我们考虑上数据结构维护该操作。上下左右移动显然是没问题的；但是行中列中轮换应该咋办呢？

我们先考虑如果只有行上轮换应该怎么办。这玩意没什么好的数据结构维护，但如果我们把它二维数点地展开成(i,p_i)就会发现，轮换一次就是(i,p_i)\rightarrow(p_i,i)，即交换两维。这也是轮换的一个奇妙性质。

然后我们把它换成三维坐标(i,j,a_{i,j})，就会发现行上轮换就是交换i,a_{i,j}，列上轮换就是交换j,a_{i,j}。这时候便很好维护了。

代码：

#include<bits/stdc++.h>
using namespace std;
int T,n,m,a[1010][1010],b[1010][1010],p[3],d[3],t[3];
char s[100100];
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++)for(int j=0;j<n;j++)scanf("%d",&a[i][j]),a[i][j]--;
        scanf("%s",s);
        for(int i=0;i<3;i++)p[i]=i,d[i]=0;
        for(int i=0;i<m;i++){
            if(s[i]=='U')(d[p[0]]+=n-1)%=n;
            if(s[i]=='D')(++d[p[0]])%=n;
            if(s[i]=='L')(d[p[1]]+=n-1)%=n;
            if(s[i]=='R')(++d[p[1]])%=n;
            if(s[i]=='I')swap(p[1],p[2]);
            if(s[i]=='C')swap(p[0],p[2]);
        }
        for(t[0]=0;t[0]<n;t[0]++)for(t[1]=0;t[1]<n;t[1]++){
            t[2]=a[t[0]][t[1]];
            b[(t[p[0]]+d[p[0]])%n][(t[p[1]]+d[p[1]])%n]=(t[p[2]]+d[p[2]])%n;
        }
        for(int i=0;i<n;i++){for(int j=0;j<n;j++)printf("%d ",b[i][j]+1);puts("");}puts("");
    }
    return 0;
}

XXVII.CF573E Bear and Bowling

考虑暴力的DP。设 f_{i,j} 表示前 i 个元素中选择长度为 j 的子序列所能得到的最大收益。

考虑由 f_i 转移到 f_{i+1}。明显，一共有两种转移方式：f_{i,j}\rightarrow f_{i+1,j}，或 f_{i,j}+(j+1)a_{i+1}\rightarrow f_{i+1,j+1}

大胆猜测，采取转移一的，一定是 f_i 上一段前缀（可以用暴力莽一下试试看）。于是我们全程采取一棵平衡树维护每个 f_i 数组。当进行转移的时候，二分求出上述分界点（这里不能使用平衡树上二分，因为需要同时检查相邻两个数的值）。然后就是单点插入、区间等差数列加了，都是基础操作。

总复杂度 O(n\log^2n)。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll res;
int n,a[100100],rt,cnt;
struct Treap{
    int ch[2],sz,rd;
    ll val,tag,dif;
}t[100100];
#define lson t[x].ch[0]
#define rson t[x].ch[1]
void pushup(int x){t[x].sz=t[lson].sz+t[rson].sz+1;}
void ADD(int x,ll val,ll dif){t[x].val+=val,t[x].tag+=val,t[x].dif+=dif;}
void pushdown(int x){
    if(lson)ADD(lson,t[x].tag-t[x].dif*(t[t[lson].ch[1]].sz+1),t[x].dif);
    if(rson)ADD(rson,t[x].tag+t[x].dif*(t[t[rson].ch[0]].sz+1),t[x].dif);
    t[x].dif=t[x].tag=0;
}
int merge(int x,int y){
    if(!x||!y)return x+y;
    if(t[x].rd>t[y].rd){pushdown(x),t[x].ch[1]=merge(t[x].ch[1],y),pushup(x);return x;}
    else{pushdown(y),t[y].ch[0]=merge(x,t[y].ch[0]),pushup(y);return y;}
}
void split(int x,int k,int &u,int &v){
    if(!x){u=v=0;return;}
    pushdown(x);
    if(t[lson].sz>=k)v=x,split(lson,k,u,lson);
    else u=x,split(rson,k-t[lson].sz-1,rson,v);
    pushup(x);
}
ll kth(int k){
    if(!k)return 0;
    int a,b,c;
    split(rt,k-1,a,b);
    split(b,1,b,c);
    ll ret=t[b].val;
    rt=merge(merge(a,b),c);
    return ret;
}
void Insert(int k,ll y){//insert an element and let it be the k-th one
    int a,b;
    split(rt,k-1,a,b);
    int x=++cnt;
    t[x].val=y,t[x].rd=rand()*rand();
    rt=merge(merge(a,x),b);
}
void Add(int k,int y){
    int a,b;
    split(rt,k-1,a,b);
    t[b].val+=1ll*(k+t[t[b].ch[0]].sz)*y;
    t[b].tag+=1ll*(k+t[t[b].ch[0]].sz)*y;
    t[b].dif+=y;
    rt=merge(a,b);
}
void Iterate(int x){
    if(!x)return;
    pushdown(x),Iterate(lson),Iterate(rson);
    res=max(res,t[x].val);
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++){
        int l=1,r=i;
        while(l<r){
            int mid=(l+r)>>1;
            if(kth(mid-1)+1ll*a[i]*mid>=kth(mid))r=mid;
            else l=mid+1;
        }
        Insert(r,kth(r-1));
        Add(r,a[i]);
    }
    Iterate(rt);
    printf("%lld\n",res);
    return 0;
}

XXVIII.[UOJ#576][ULR#1]服务器调度

非常可怕的大数据结构题，原版代码整整码了9K，就算稍微合并合并也剩下7K……

首先，我们考虑对每种颜色，建出一棵虚树。考虑求出虚树的一条直径。则有个结论是原树上到任意一点最远的点肯定是此直径的端点之一。

例如，我们考虑下方的这棵树：

                O           
               / \              
              Z   V         
             / \                
            M   Y
           / \
          X   U

设我们求出虚树的直径是 X,Y。我们考虑求出该直径的中点是 M。则显然，M 一定位于 X 和 Y 中深度更大的那一个节点到二者 LCA 的路径上。例如，在上图中，就可以看到图上的 M 在深度更大的 X 一侧。我们在接下来的讲解中，都会默认 X 是更深的那一个。同时，可以找到它们的 LCA 是 Z。

则，M 及 M 子树中所有节点，关于此种颜色的最远点都是 Y；而 M 子树外所有节点的最远点都是 X。

我们先考虑子树中的一个点，上述的 U。明显，此种颜色对其贡献，是 dis_U+dis_Y-2dis_{\text{lca}(U,Y)}。

我们发现，必有 \text{lca}(U,Y)=Z。故上式可以被转换成 dis_U+dis_Y-2dis_Z。

此式可以被拆作两部分——dis_U，此部分我们接下来再说。dis_Y-2dis_Z，其对于 M 子树中所有点（即所有可能的 U）都是常数，故我们可以直接上一棵线段树对其进行子树加来维护此部分。

我们再考虑子树外的一个点，上述的 V。则此种颜色对其贡献是 dis_V+dis_X-2dis_{\text{lca}(V,X)}。

此式可以被拆作三部分。第一部分，dis_V。结合上前面的 dis_U，我们发现其范围就是整棵树。则，每种颜色都会对整棵树覆盖一次，一共有 m 种颜色，则一共会覆盖 m 次。在询问时，我们直接上一个前缀和维护子树中所有东西的 dis 之和，再乘上一个 m 即为此部分答案。

第二部分，dis_X。其仍是常数，仍可使用我们上述的子树加线段树处理。

第三部分，-2dis_{\text{lca}(V,X)}。其可被先转换成 -2dis_{\text{lca}(V,M)}，但仍然不好处理。

我们考虑对 M 到根的路径上所有边都打上一个 -2 的 tag（使用树剖）。这样，点 V 到根的路径上所有边的长度的带权（权为 tag）和就是 dis_{\text{lca}(V,M)}。但是，一个问题是，此方案不仅会影响 M 子树外的点，更会影响 M 子树中的点。

但是，我们发现，此方案对 M 子树中所有点的影响都是固定的——都是 -2dis_M。故我们直接仍在上述子树加线段树上把这部分影响给它补回去即可，即执行子树加 2dis_M。

我们再来考虑求答案时的操作。子树加线段树上的操作以及前缀和之类的都可以简单完成。关键还是上述 V 的第三部分操作比较烦人——它要求出子树中所有点到根路径的带权距离和。设当前询问的点是 Q。

考虑每条边被覆盖多少次。明显，Q 到根路径上所有边，覆盖其的路径数量都为 Q 的子树大小。故我们只需求出 Q 到根路径的带权长度，再乘上 Q 的子树大小，即为此部分贡献。到根路径的带权长度，仍可使用树剖解决。

而考虑 Q 子树中的任意一条边 X-Y，其中 X 是 Y 的父亲，其被覆盖了 Y 子树大小次。故我们仍可以求带权子树和，此处权仍然是边上的 tag，但值是 \text{边的长度}\times\text{Y子树大小}。则其可再开一棵线段树解决。

于是我们便解决了这个问题。剩下的就是我们之前忽略的一些问题了。例如，对于每种颜色，如何维护其直径？

众所周知的是，有一个结论，两组点集合并时，新点集的直径的端点一定来自于两点集中原本的直径端点（不管其是来自于同一点集还是不同点集）。这就意味着我们可以使用线段树维护不同颜色的端点了（当然，用的是动态开点线段树。实际上直接开 m 棵平衡树维护也不失为一个好选择，但是那样子码量和常数都会噌噌上涨）。

最后是具体实现时的一些问题。例如，虽然总复杂度是 O(n\log^2n) 的（来自于树剖），但是事实上是常数极大（毕竟我们前面开了好几棵线段树），需要榨取所有可以被优化的常数。所以，求直径时用 O(1) 的 RMQ-LCA 罢。而同时，为了实现求一条直径的中点，我们还要再预处理倍增数组以方便树上二分。于是你将会发现本题需要全部三种LCA算法。

同时，因为各种东西全掺在一块会使得条理很不清晰，大剂量的 namespace 等封装在 debug 时是很有必要的（同时，也方便把已经 debug 完的部分缩起来避免看偏）

但是，就算这样说，最后还免不得TLE的悲惨命运。以下是TLE的初版代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
const int N=200100;
int col[N];
int dep[N],dis[N],fa[N],dfn[N],rev[N],top[N],sz[N],num[N];
namespace TRE{//works about the original tree
    int head[N],cnt;
    struct node{int to,next,val;}edge[N];
    void ae(int u,int v,int w){edge[cnt].next=head[u],edge[cnt].to=v,edge[cnt].val=w,head[u]=cnt++;}
    namespace SPR{//tree-chain separation.
        int tot,son[N];
        void dfs1(int x){
            sz[x]=1;
            for(int i=head[x],y;i!=-1;i=edge[i].next){
                dep[y=edge[i].to]=dep[x]+1,dis[y]=dis[x]+edge[i].val,fa[y]=x,dfs1(y),sz[x]+=sz[y];
                if(sz[y]>=sz[son[x]])son[x]=y;
            }
        }
        void dfs2(int x){
            dfn[x]=++tot,rev[tot]=x;
            if(!top[x])top[x]=x;
            if(son[x])top[son[x]]=top[x],dfs2(son[x]);
            for(int i=head[x];i!=-1;i=edge[i].next)if(edge[i].to!=son[x])dfs2(edge[i].to);
        }
    }
    namespace ST{//ST table for LCA part
        int MN[N<<1][20],LG[N<<1],FIR[N],lim;
        void dfs(int x){
            MN[++lim][0]=x,FIR[x]=lim;
            for(int i=head[x];i!=-1;i=edge[i].next)dfs(edge[i].to),MN[++lim][0]=x;
        }
        int MIN(int x,int y){return dep[x]<dep[y]?x:y;}
        void init(){
            for(int i=2;i<=lim;i++)LG[i]=LG[i>>1]+1;
            for(int j=1;j<=LG[lim];j++)for(int i=1;i+(1<<j)-1<=lim;i++)MN[i][j]=MIN(MN[i][j-1],MN[i+(1<<(j-1))][j-1]);
        }
        int LCA(int x,int y){
            x=FIR[x],y=FIR[y];
            if(x>y)swap(x,y);
            int k=LG[y-x+1];
            return MIN(MN[x][k],MN[y-(1<<k)+1][k]);
        }
        int DIS(int x,int y){return dis[x]+dis[y]-2*dis[LCA(x,y)];}
    }
    using ST::LCA;
    namespace DOB{//doubling on tree part for ancestor tracing
        int anc[N<<1][20];
        void init(){
            for(int i=1;i<=n;i++)anc[i][0]=fa[i];
            for(int j=1;j<=19;j++)for(int i=1;i<=n;i++)anc[i][j]=anc[anc[i][j-1]][j-1];
        }
        int MID(int &x,int &y){//using doubling on tree to calculate the midpoint of a route
            int z=LCA(x,y);
            if(dis[x]<=dis[y])swap(x,y);
            int r=x;
            for(int i=19;i>=0;i--)if(dep[r]-(1<<i)>=dep[z]&&dis[x]-dis[anc[r][i]]<=dis[y]+dis[anc[r][i]]-2*dis[z])r=anc[r][i];
            return r;
        }
    }
    void init(){SPR::dfs1(1),SPR::dfs2(1),ST::dfs(1),ST::init(),DOB::init();}
}
using TRE::LCA;
using TRE::DOB::MID;
using TRE::ST::DIS;
namespace DIA{//calculating the diameter of the tree
    int rt[N],cnt,bin[N*20],tp;
    struct SegTree{//a dynamic-nodeadding segtree, calculating diameters of each colour's virtual trees 
        int lson,rson,u,v;
    }seg[N*20];
    #define mid ((l+r)>>1)
    void pushup(int &x){
        seg[x].u=seg[x].v=0;
        if(!seg[x].lson&&!seg[x].rson){bin[++tp]=x,x=0;return;}
        if(!seg[x].rson){seg[x].u=seg[seg[x].lson].u,seg[x].v=seg[seg[x].lson].v;return;}
        if(!seg[x].lson){seg[x].u=seg[seg[x].rson].u,seg[x].v=seg[seg[x].rson].v;return;}
        int a[4]={seg[seg[x].lson].u,seg[seg[x].lson].v,seg[seg[x].rson].u,seg[seg[x].rson].v};
        for(int i=0;i<4;i++)for(int j=i+1;j<4;j++)if((!seg[x].u&&!seg[x].v)||DIS(seg[x].u,seg[x].v)<DIS(a[i],a[j]))seg[x].u=a[i],seg[x].v=a[j];
    }
    int NewNode(){return tp?bin[tp--]:++cnt;}
    void Insert(int &x,int l,int r,int P){
//      printf("%d %d:%d\n",l,r,P);
        if(l>P||r<P)return;
        if(!x)x=NewNode();
        if(l==r){seg[x].u=seg[x].v=rev[P];return;}
        Insert(seg[x].lson,l,mid,P),Insert(seg[x].rson,mid+1,r,P),pushup(x);
    }
    void Delete(int &x,int l,int r,int P){
        if(l>P||r<P)return;
        if(l==r){seg[x].u=seg[x].v=0,bin[++tp]=x,x=0;return;}
        Delete(seg[x].lson,l,mid,P),Delete(seg[x].rson,mid+1,r,P),pushup(x);
    }
//  void Iterate(int x,int l,int r){
//      if(!x)return;
//      printf("%d:[%d,%d]:(%d,%d)\n",x,l,r,seg[x].u,seg[x].v);
//      Iterate(seg[x].lson,l,mid),Iterate(seg[x].rson,mid+1,r);
//  }
    #undef mid
}
ll sumdis[N];
namespace SUB{
    #define lson x<<1
    #define rson x<<1|1
    #define mid ((l+r)>>1)
    struct SegTree{ll sum,tag;}seg[N<<2];
    void ADD(int x,int l,int r,ll y){seg[x].sum+=y*(r-l+1),seg[x].tag+=y;}
    void pushup(int x){seg[x].sum=seg[lson].sum+seg[rson].sum;}
    void pushdown(int x,int l,int r){ADD(lson,l,mid,seg[x].tag),ADD(rson,mid+1,r,seg[x].tag),seg[x].tag=0;}
    void modify(int x,int l,int r,int L,int R,int val){
        if(l>R||r<L)return;
        if(L<=l&&r<=R){ADD(x,l,r,val);return;}
        pushdown(x,l,r),modify(lson,l,mid,L,R,val),modify(rson,mid+1,r,L,R,val),pushup(x);
    }
    ll query(int x,int l,int r,int L,int R){
        if(l>R||r<L)return 0;
        if(L<=l&&r<=R)return seg[x].sum;
        pushdown(x,l,r);return query(lson,l,mid,L,R)+query(rson,mid+1,r,L,R);
    }
    #undef lson
    #undef rson
    #undef mid
}
namespace ALT{//segtree of alter-subtree jobs(using SPR things)
    namespace SBT{//segment tree for subtree works
        #define lson x<<1
        #define rson x<<1|1
        #define mid ((l+r)>>1)
        struct SegTree{ll sumsz,tag,sum;}seg[N<<2];
        void ADD(int x,ll y){seg[x].tag+=y,seg[x].sum+=y*seg[x].sumsz;}
        void pushdown(int x){ADD(lson,seg[x].tag),ADD(rson,seg[x].tag),seg[x].tag=0;}
        void pushup(int x){seg[x].sum=seg[lson].sum+seg[rson].sum;}
        void build(int x,int l,int r){
            if(l==r){seg[x].sumsz=1ll*sz[rev[l]]*num[rev[l]];return;}
            build(lson,l,mid),build(rson,mid+1,r),seg[x].sumsz=seg[lson].sumsz+seg[rson].sumsz;
        }
        void modify(int x,int l,int r,int L,int R,ll val){
            if(l>R||r<L)return;
            if(L<=l&&r<=R){ADD(x,val);return;}
            pushdown(x),modify(lson,l,mid,L,R,val),modify(rson,mid+1,r,L,R,val),pushup(x);
        }
        ll query(int x,int l,int r,int L,int R){
            if(l>R||r<L)return 0;
            if(L<=l&&r<=R)return seg[x].sum;
            pushdown(x);return query(lson,l,mid,L,R)+query(rson,mid+1,r,L,R);
        }
        #undef lson
        #undef rson
        #undef mid          
    }
    namespace CHT{//segtree of chain jobs
        #define lson x<<1
        #define rson x<<1|1
        #define mid ((l+r)>>1)
        struct SegTree{ll sumnum,tag,sum;}seg[N<<2];
        void ADD(int x,ll y){seg[x].tag+=y,seg[x].sum+=y*seg[x].sumnum;}
        void pushdown(int x){ADD(lson,seg[x].tag),ADD(rson,seg[x].tag),seg[x].tag=0;}
        void pushup(int x){seg[x].sum=seg[lson].sum+seg[rson].sum;}
        void build(int x,int l,int r){
            if(l==r){seg[x].sumnum=num[rev[l]];return;}
            build(lson,l,mid),build(rson,mid+1,r),seg[x].sumnum=seg[lson].sumnum+seg[rson].sumnum;
        }
        void modify(int x,int l,int r,int L,int R,ll val){
            if(l>R||r<L)return;
            if(L<=l&&r<=R){ADD(x,val);return;}
            pushdown(x),modify(lson,l,mid,L,R,val),modify(rson,mid+1,r,L,R,val),pushup(x);
        }
        ll query(int x,int l,int r,int L,int R){
            if(l>R||r<L)return 0;
            if(L<=l&&r<=R)return seg[x].sum;
            pushdown(x);return query(lson,l,mid,L,R)+query(rson,mid+1,r,L,R);
        }
        #undef lson
        #undef rson
        #undef mid  
    }
    void modify(int l,int r,int val){SBT::modify(1,1,n,l,r,val),CHT::modify(1,1,n,l,r,val);}
    void chainmod(int x,int val){while(x)modify(dfn[top[x]],dfn[x],val),x=fa[top[x]];}
    ll chainsum(int x){ll ret=0;while(x)ret+=CHT::query(1,1,n,dfn[top[x]],dfn[x]),x=fa[top[x]];return ret;}
}
void diameter(int x,int y,int dir){//works need to do when have a diameter of (x-y).
    int m=MID(x,y);
    int z=LCA(x,y);
//  printf("%d %d %d %d\n",x,y,m,z);
//  printf("%d %d %d %d\n",x,y,m,z);
    SUB::modify(1,1,n,dfn[m],dfn[m]+sz[m]-1,dir*(dis[y]-2*dis[z]+2*dis[m]));
//  printf("SUB%d:%d\n",m,dis[y]-2*dis[z]);
//  printf("ALTER%d:%d\n",m,dis[x]);
//  printf("CHAIN%d:%d\n",m,-2);
    SUB::modify(1,1,n,1,dfn[m]-1,dir*dis[x]);
    SUB::modify(1,1,n,dfn[m]+sz[m],n,dir*dis[x]);
    ALT::chainmod(m,-2*dir);
}
int m,q;
ll query(int x){
    ll res=0;
    res+=(sumdis[dfn[x]+sz[x]-1]-sumdis[dfn[x]-1])*m;
    res+=SUB::query(1,1,n,dfn[x],dfn[x]+sz[x]-1);
//  printf("CHAS:%d\n",ALT::chainsum(fa[x]));
//  printf("SBT:%d\n",ALT::SBT::query(1,1,n,dfn[x],dfn[x]+sz[x]-1));
    res+=ALT::chainsum(fa[x])*sz[x];
    res+=ALT::SBT::query(1,1,n,dfn[x],dfn[x]+sz[x]-1);
    return res;
}
#define dia(i) DIA::seg[DIA::rt[i]].u,DIA::seg[DIA::rt[i]].v
int main(){
    scanf("%d%d%d",&n,&m,&q),memset(TRE::head,-1,sizeof(TRE::head));
    for(int i=1;i<=n;i++)scanf("%d",&col[i]);
    for(int i=2;i<=n;i++)scanf("%d",&fa[i]);
    for(int i=2;i<=n;i++)scanf("%d",&num[i]),TRE::ae(fa[i],i,num[i]);
    TRE::init();
    ALT::SBT::build(1,1,n);
    ALT::CHT::build(1,1,n);
//  for(int i=1;i<=n;i++)printf("%d:FA:%d SZ:%d SN:%d DF:%d RV:%d TP:%d DP:%d\n",i,fa[i],sz[i],TRE::SPR::son[i],dfn[i],rev[i],top[i],dep[i]);
    for(int i=1;i<=n;i++)sumdis[i]=sumdis[i-1]+dis[rev[i]];
    for(int i=1;i<=n;i++)DIA::Insert(DIA::rt[col[i]],1,n,dfn[i]);

//  diameter(dia(4),1);
//  m=1;
//  printf("%d\n",query(4));
//  m=4;
//  diameter(dia(4),-1);

    for(int i=1;i<=m;i++)diameter(dia(i),1);

    for(int t,x;q;q--){
        scanf("%d%d",&t,&x);
        if(t==1){
            diameter(dia(col[x]),-1),DIA::Delete(DIA::rt[col[x]],1,n,dfn[x]),diameter(dia(col[x]),1);
            scanf("%d",&col[x]);
            diameter(dia(col[x]),-1),DIA::Insert(DIA::rt[col[x]],1,n,dfn[x]),diameter(dia(col[x]),1);
        }else printf("%lld\n",query(x));
    }
    return 0;
}

最终，我用树状数组替换掉了其中三棵线段树（将其模板化）。最终便卡过去了。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
const int N=200100;
int col[N];
int dep[N],dis[N],fa[N],dfn[N],rev[N],top[N],sz[N],num[N];
namespace TRE{//works about the original tree
    int head[N],cnt;
    struct node{int to,next,val;}edge[N];
    void ae(int u,int v,int w){edge[cnt].next=head[u],edge[cnt].to=v,edge[cnt].val=w,head[u]=cnt++;}
    namespace SPR{//tree-chain separation.
        int tot,son[N];
        void dfs1(int x){
            sz[x]=1;
            for(int i=head[x],y;i!=-1;i=edge[i].next){
                dep[y=edge[i].to]=dep[x]+1,dis[y]=dis[x]+edge[i].val,fa[y]=x,dfs1(y),sz[x]+=sz[y];
                if(sz[y]>=sz[son[x]])son[x]=y;
            }
        }
        void dfs2(int x){
            dfn[x]=++tot,rev[tot]=x;
            if(!top[x])top[x]=x;
            if(son[x])top[son[x]]=top[x],dfs2(son[x]);
            for(int i=head[x];i!=-1;i=edge[i].next)if(edge[i].to!=son[x])dfs2(edge[i].to);
        }
    }
    namespace ST{//ST table for LCA part
        int MN[N<<1][20],LG[N<<1],FIR[N],lim;
        void dfs(int x){
            MN[++lim][0]=x,FIR[x]=lim;
            for(int i=head[x];i!=-1;i=edge[i].next)dfs(edge[i].to),MN[++lim][0]=x;
        }
        int MIN(int x,int y){return dep[x]<dep[y]?x:y;}
        void init(){
            for(int i=2;i<=lim;i++)LG[i]=LG[i>>1]+1;
            for(int j=1;j<=LG[lim];j++)for(int i=1;i+(1<<j)-1<=lim;i++)MN[i][j]=MIN(MN[i][j-1],MN[i+(1<<(j-1))][j-1]);
        }
        int LCA(int x,int y){
            x=FIR[x],y=FIR[y];
            if(x>y)swap(x,y);
            int k=LG[y-x+1];
            return MIN(MN[x][k],MN[y-(1<<k)+1][k]);
        }
        int DIS(int x,int y){return dis[x]+dis[y]-2*dis[LCA(x,y)];}
    }
    using ST::LCA;
    namespace DOB{//doubling on tree part for ancestor tracing
        int anc[N<<1][20];
        void init(){
            for(int i=1;i<=n;i++)anc[i][0]=fa[i];
            for(int j=1;j<=19;j++)for(int i=1;i<=n;i++)anc[i][j]=anc[anc[i][j-1]][j-1];
        }
        int MID(int &x,int &y){//using doubling on tree to calculate the midpoint of a route
            int z=LCA(x,y);
            if(dis[x]<=dis[y])swap(x,y);
            int r=x;
            for(int i=19;i>=0;i--)if(dep[r]-(1<<i)>=dep[z]&&dis[x]-dis[anc[r][i]]<=dis[y]+dis[anc[r][i]]-2*dis[z])r=anc[r][i];
            return r;
        }
    }
    void init(){SPR::dfs1(1),SPR::dfs2(1),ST::dfs(1),ST::init(),DOB::init();}
}
using TRE::LCA;
using TRE::DOB::MID;
using TRE::ST::DIS;
namespace DIA{//calculating the diameter of the tree
    int rt[N],cnt,bin[N*20],tp;
    struct SegTree{//a dynamic-nodeadding segtree, calculating diameters of each colour's virtual trees 
        int lson,rson,u,v;
    }seg[N*20];
    #define mid ((l+r)>>1)
    void pushup(int &x){
        seg[x].u=seg[x].v=0;
        if(!seg[x].lson&&!seg[x].rson){bin[++tp]=x,x=0;return;}
        if(!seg[x].rson){seg[x].u=seg[seg[x].lson].u,seg[x].v=seg[seg[x].lson].v;return;}
        if(!seg[x].lson){seg[x].u=seg[seg[x].rson].u,seg[x].v=seg[seg[x].rson].v;return;}
        int a[4]={seg[seg[x].lson].u,seg[seg[x].lson].v,seg[seg[x].rson].u,seg[seg[x].rson].v};
        for(int i=0;i<4;i++)for(int j=i+1;j<4;j++)if((!seg[x].u&&!seg[x].v)||DIS(seg[x].u,seg[x].v)<DIS(a[i],a[j]))seg[x].u=a[i],seg[x].v=a[j];
    }
    int NewNode(){return tp?bin[tp--]:++cnt;}
    void Insert(int &x,int l,int r,int P){
//      printf("%d %d:%d\n",l,r,P);
        if(l>P||r<P)return;
        if(!x)x=NewNode();
        if(l==r){seg[x].u=seg[x].v=rev[P];return;}
        Insert(seg[x].lson,l,mid,P),Insert(seg[x].rson,mid+1,r,P),pushup(x);
    }
    void Delete(int &x,int l,int r,int P){
        if(l>P||r<P)return;
        if(l==r){seg[x].u=seg[x].v=0,bin[++tp]=x,x=0;return;}
        Delete(seg[x].lson,l,mid,P),Delete(seg[x].rson,mid+1,r,P),pushup(x);
    }
//  void Iterate(int x,int l,int r){
//      if(!x)return;
//      printf("%d:[%d,%d]:(%d,%d)\n",x,l,r,seg[x].u,seg[x].v);
//      Iterate(seg[x].lson,l,mid),Iterate(seg[x].rson,mid+1,r);
//  }
    #undef mid
}
struct BIT{//a universal template of fenwick tree
    ll s[N];//the prefix sum of original array
    ll t1[N],t2[N];//the unweighted and weighted fenwick
    ll&operator[](const int &x){return s[x];}
    BIT(){memset(s,0,sizeof(s)),memset(t1,0,sizeof(t1)),memset(t2,0,sizeof(t2));}
    void ADD(int x,int y){for(int i=x;i<=n;i+=i&-i)t1[i]+=y,t2[i]+=1ll*s[x-1]*y;}
    ll SUM(int x){
        ll sum=0;
        for(int i=x;i;i-=i&-i)sum+=t1[i];
        sum*=s[x];
        for(int i=x;i;i-=i&-i)sum-=t2[i];
        return sum;
    }
    void ADD(int l,int r,int val){if(l<=r)ADD(l,val),ADD(r+1,-val);}
    ll SUM(int l,int r){return SUM(r)-SUM(l-1);}
}SUB,SBT,CHT;
ll sumdis[N];
namespace ALT{//segtree of alter-subtree jobs(using SPR things)
    void modify(int l,int r,int val){SBT.ADD(l,r,val),CHT.ADD(l,r,val);}
    void chainmod(int x,int val){while(x)modify(dfn[top[x]],dfn[x],val),x=fa[top[x]];}
    ll chainsum(int x){ll ret=0;while(x)ret+=CHT.SUM(dfn[top[x]],dfn[x]),x=fa[top[x]];return ret;}
}
void diameter(int x,int y,int dir){//works need to do when have a diameter of (x-y).
    int m=MID(x,y);
    int z=LCA(x,y);
    SUB.ADD(dfn[m],dfn[m]+sz[m]-1,dir*(dis[y]-2*dis[z]+2*dis[m]));
    SUB.ADD(1,dfn[m]-1,dir*dis[x]);
    SUB.ADD(dfn[m]+sz[m],n,dir*dis[x]);
    ALT::chainmod(m,-2*dir);
}
int m,q;
ll query(int x){
    ll res=0;
    res+=(sumdis[dfn[x]+sz[x]-1]-sumdis[dfn[x]-1])*m;
    res+=SUB.SUM(dfn[x],dfn[x]+sz[x]-1);
//  printf("CHAS:%d\n",ALT::chainsum(fa[x]));
//  printf("SBT:%d\n",ALT::SBT::query(1,1,n,dfn[x],dfn[x]+sz[x]-1));
    res+=ALT::chainsum(fa[x])*sz[x];
    res+=SBT.SUM(dfn[x],dfn[x]+sz[x]-1);
    return res;
}
#define dia(i) DIA::seg[DIA::rt[i]].u,DIA::seg[DIA::rt[i]].v
int main(){
    scanf("%d%d%d",&n,&m,&q),memset(TRE::head,-1,sizeof(TRE::head));
    for(int i=1;i<=n;i++)scanf("%d",&col[i]);
    for(int i=2;i<=n;i++)scanf("%d",&fa[i]);
    for(int i=2;i<=n;i++)scanf("%d",&num[i]),TRE::ae(fa[i],i,num[i]);
    TRE::init();
    for(int i=1;i<=n;i++)SUB[i]=i;
    for(int i=1;i<=n;i++)SBT[i]=SBT[i-1]+1ll*sz[rev[i]]*num[rev[i]];
    for(int i=1;i<=n;i++)CHT[i]=CHT[i-1]+num[rev[i]];
//  for(int i=1;i<=n;i++)printf("%d:FA:%d SZ:%d SN:%d DF:%d RV:%d TP:%d DP:%d\n",i,fa[i],sz[i],TRE::SPR::son[i],dfn[i],rev[i],top[i],dep[i]);
    for(int i=1;i<=n;i++)sumdis[i]=sumdis[i-1]+dis[rev[i]];
    for(int i=1;i<=n;i++)DIA::Insert(DIA::rt[col[i]],1,n,dfn[i]);

//  diameter(dia(4),1);
//  m=1;
//  printf("%d\n",query(4));
//  m=4;
//  diameter(dia(4),-1);

    for(int i=1;i<=m;i++)diameter(dia(i),1);

    for(int t,x;q;q--){
        scanf("%d%d",&t,&x);
        if(t==1){
            diameter(dia(col[x]),-1),DIA::Delete(DIA::rt[col[x]],1,n,dfn[x]),diameter(dia(col[x]),1);
            scanf("%d",&col[x]);
            diameter(dia(col[x]),-1),DIA::Insert(DIA::rt[col[x]],1,n,dfn[x]),diameter(dia(col[x]),1);
        }else printf("%lld\n",query(x));
    }
    return 0;
}

XXIX.CF576E Painting Edges

首先，这个trick很常见，应该默认就能想到线段树分治的做法。但是，同样可以实现该trick的LCT维护关于删除时间的最大生成树的做法，因为我们并不知道删除时间是什么，所以不太好写（但是是能写的）。故我们只考虑线段树分治做法。

线段树分治，只需要用一个带权并查集维护二分图即可。时间复杂度 O(n\log^2n)。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,c,q,U[500100],V[500100],nex[500100],las[500100],id[500100],col[500100];
bool res[500100];

struct dat{int u,v,lu,lv;bool ru,rv;dat(int a,int b,int c,int d,bool e,bool f){u=a,v=b,lu=c,lv=d,ru=e,rv=f;}};
struct UFS{
    int dsu[500100],len[500100];
    bool rev[500100];
    stack<dat>s;
    void init(){for(int i=1;i<=n;i++)dsu[i]=i;}
    int findfa(int x){return dsu[x]==x?x:findfa(dsu[x]);}
    bool findcol(int x){return dsu[x]==x?rev[x]:findcol(dsu[x])^rev[x];}
    bool merge(int u,int v){
        bool cu=findcol(u),cv=findcol(v);
        u=findfa(u),v=findfa(v);
        if(u==v)return false;
        if(len[u]>len[v])swap(u,v),swap(cu,cv);
        s.push(dat(u,v,len[u],len[v],rev[u],rev[v]));
        len[v]=max(len[v],len[u]+1),dsu[u]=v,rev[u]^=(cu==cv);
        return true;
    }
    bool ask(int u,int v){return findfa(u)!=findfa(v)||findcol(u)!=findcol(v);}
    void undo(){
        dsu[s.top().u]=s.top().u,len[s.top().u]=s.top().lu,rev[s.top().u]=s.top().ru;
        dsu[s.top().v]=s.top().v,len[s.top().v]=s.top().lv,rev[s.top().v]=s.top().rv;
        s.pop();
    }   
}t[51];

#define lson x<<1
#define rson x<<1|1
#define mid ((l+r)>>1)
vector<int>v[2001000];
void modify(int x,int l,int r,int L,int R,int k){if(l>R||r<L)return;if(L<=l&&r<=R)v[x].push_back(k);else modify(lson,l,mid,L,R,k),modify(rson,mid+1,r,L,R,k);}
void solve(int x,int l,int r){
//  printf("%d[%d,%d]\n",x,l,r);
    vector<int>u;
    for(auto i:v[x])if(t[col[i]].merge(U[id[i]],V[id[i]]))u.push_back(col[i]);
    if(l==r){
        if(t[col[l]].ask(U[id[l]],V[id[l]]))res[l]=true,modify(1,1,q,l+1,nex[l]-1,l);
        else{
            res[l]=false;
            if(las[l])modify(1,1,q,l+1,nex[l]-1,las[l]);
            if(nex[l]<=q)las[nex[l]]=las[l];
        }
    }else solve(lson,l,mid),solve(rson,mid+1,r);
    for(auto i:u)t[i].undo();
}
int main(){
    scanf("%d%d%d%d",&n,&m,&c,&q);
    for(int i=1;i<=c;i++)t[i].init();
    for(int i=1;i<=m;i++)scanf("%d%d",&U[i],&V[i]);
    for(int i=1;i<=q;i++)scanf("%d%d",&id[i],&col[i]),nex[las[id[i]]]=i,las[id[i]]=i;
    memset(las,0,sizeof(las));for(int i=1;i<=q;i++)if(!nex[i])nex[i]=q+1;else las[nex[i]]=i;
    solve(1,1,q);
    for(int i=1;i<=q;i++)puts(res[i]?"YES":"NO");
    return 0;
}

XXX.CF505E Mr. Kitayuta vs. Bamboos

“最大值最小”，条件反射套个二分上去。

于是现在问题转变成判定型问题。

正着搞不好处理 \max(h_i-p,0) 这种套了 \max 的限制，干脆正难则反，考虑倒着处理。

于是问题转变为 第 i 天开头所有竹子高度减少 a_i，然后你可以选几棵再给它补回来 p。目标是所有竹子在结尾时高度不低于 h_i，但同时还要保证任意时刻竹子高度不会被减成负数。

如何构造补竹子的顺序呢？考虑贪心——每次总是补那些最快被减成负数的竹子。换句话说，可以用一颗堆来维护所有在结尾时高度低于 h_i 的竹子，因为竹子只要保证最终高度符合要求，对中间的高度除了非零外别无要求，所以此种贪心正确。当前高度不合法，当且仅当某一时刻竹子出现负数或者是最终堆非空（意味着尚有高度不合要求的竹子）。

时间复杂度 O(n\log^2n)。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,k,p,h[100100],a[100100];
struct dat{
    ll tim,tot;
    int id;
    dat(ll A,ll B,int C){tim=A,tot=B,id=C;}
    friend bool operator<(const dat&u,const dat&v){return u.tim>v.tim;}
};
priority_queue<dat>q;
bool che(ll ip){
    while(!q.empty())q.pop();
    for(int i=1;i<=n;i++)if(ip-1ll*m*a[i]<h[i])q.push(dat(ip/a[i],ip,i));
    for(int i=1;i<=m;i++){
        if(!q.empty()&&q.top().tim<i)return false;
        for(int j=1;j<=k;j++)if(!q.empty()){
            dat x=q.top();q.pop();
            x.tot+=p,x.tim=x.tot/a[x.id];
            if(x.tot-1ll*m*a[x.id]<h[x.id])q.push(x);
        }
    }
    return q.empty();
}
int main(){
    scanf("%d%d%d%d",&n,&m,&k,&p);
    for(int i=1;i<=n;i++)scanf("%d%d",&h[i],&a[i]);
    ll l=1,r=1e14;
    while(l<r){
        ll mid=(l+r)>>1;
        if(che(mid))r=mid;
        else l=mid+1;
    }
    printf("%lld\n",r);
    return 0;
}

XXXI.CF626G Raffles

首先，我们列出“往一个奖池内多投一张彩票”，在奖项为 c、初始有 a 张、当前已经又投了 r 张时的额外收益：

稍微化简一下就能得到

明显，随着 r 的增大，分子不变，分母是增函数，于是整个额外收益就是减函数——这意味着你往一个奖池里投越多彩票，单张彩票所取得的收益就越小。这意味着我们可以搞一个贪心，用一个堆维护所有奖池内再投一张彩票所能取得的收益，然后每次弹出其中的最大值，并将最大值所在的奖池的下一张彩票加入堆中。

现在，它开始修改 a 了，我们应该怎么做呢？

暴力从当前已投入的所有彩票中，找出收益最小的那一张，并将其与当前未投入的所有彩票中收益最大的那一张比较，若没有未投入的那张大就暴力更换（这意味着要用 multiset 来替换堆），直到替换会使答案更劣为止。该做法的正确性显然，但是复杂度是不是不太对劲？

我们思考一下，仅仅是 a 变换了 1，对全局的影响应该不会太大——事实上，受到影响而不再投入的彩票数量是 O(1) 的！

这样，暴力的正确性和复杂度都有保证。

实现时，不管它“不超过一半”的限制，仅仅把投入一半以上彩票时额外投入一张的收益为 0 会让代码实现简单很多。

时间复杂度 O(n\log n)，

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const double eps=1e-12;
int n,m,q,a[200100],c[200100],r[200100];
double F(int X,int R){
    if(R<0)return 0x3f3f3f3f;
    if(R>=a[X])return 0;
    return 1.0*c[X]*a[X]/(a[X]+R+1)/(a[X]+R);
}
double G(int x){return 1.0*c[x]*min(r[x],a[x])/(a[x]+min(r[x],a[x]));}
struct dat{
    double val;
    int id,lot;
    dat(int X,int Y){id=X,lot=Y,val=F(id,lot);}
    friend bool operator<(const dat&u,const dat&v){return fabs(u.val-v.val)<eps?u.id<v.id:u.val<v.val;}
};
multiset<dat>all,cho;
double res;
void Push(){
    auto it=--cho.end();
    res+=it->val;
    int x=it->id;
    all.erase(dat(x,r[x]-1)),all.insert(*it);
    cho.erase(it),cho.insert(dat(x,++r[x]));
}
void Pop(){
    auto it=all.begin();
    res-=it->val;
    int x=it->id;
    cho.erase(dat(x,r[x])),cho.insert(*it);
    all.erase(it),all.insert(dat(x,--r[x]-1));
}
void read(int &x){
    x=0;
    char c=getchar();
    while(c>'9'||c<'0')c=getchar();
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
}
int main(){
    read(n),read(m),read(q);
    for(int i=1;i<=n;i++)read(c[i]);
    for(int i=1;i<=n;i++)read(a[i]);
    for(int i=1;i<=n;i++)all.insert(dat(i,-1)),cho.insert(dat(i,0));
    while(m--)Push();
//  printf("%lf\n",res);
    for(int i=1,x,y;i<=q;i++){
        read(y),read(x);
        all.erase(dat(x,r[x]-1)),cho.erase(dat(x,r[x])),res-=G(x);
        if(y==1)a[x]++;else a[x]--;
        all.insert(dat(x,r[x]-1)),cho.insert(dat(x,r[x])),res+=G(x);
        while(cho.rbegin()->val>all.begin()->val+eps)Pop(),Push();
        printf("%.8lf\n",res);
    }
    return 0;
}

XXXII.CF1491H Yuezheng Ling and Dynamic Tree

首先，相信大家都做过[HNOI2010]弹飞绵羊这道经典原题，而这题显然是那题的增强版。

众所周知，该原题有两种常见解法：LCT或分块。凭直觉发现LCT不可能处理这种区间修改问题，于是我们考虑分块。

分块的话，就需要维护一个位置在跳完它所在的那个块后的落点。但这里为了方便求LCA，所以我们借鉴树剖的思想，令 go_x 为离开块前最后一个到达的节点，令 len_x 表示其在块内跳的次数。

我们发现，若一个块被修改了超过块长次，则其中所有元素的 go_x 都必定为其自身，len_x 都必定为 0，就可以直接打 tag 维护里面所有元素的 a_x 了。

于是对于每次修改，我们暴力重构未满的块，若块长是 \sqrt{n}，则一共 \sqrt n 个块，每块被修改 \sqrt n 次，每次修改 \sqrt n 个元素，总复杂度 O(n\sqrt n)，可以接受。

下面考虑求LCA。明显，我们可以先跑出从 x,y 到根的路径上所有需要的点（指所有 go_x 及其父亲）的 dep，然后就可以像树剖一样处理，直到两个东西的 go 相同。此时它们必在同一块内，直接暴力即可。此部分复杂度 O(\sqrt n)。

故总复杂度 O(n\sqrt n)。

代码：

#include<bits/stdc++.h>
using namespace std;
const int BBB=500;
int n,m,a[100100],BLK[100100],go[100100],len[100100],dep[100100],lp[510],tag[510],num;
bool fin[510];
void rebuild(int id,int L,int R,int x){
    if(L<=lp[id]&&R>=lp[id+1]-1&&fin[id]){tag[id]+=x,tag[id]=min(tag[id],n);return;}
    fin[id]=true;
    for(int i=lp[id];i<lp[id+1];i++){
        a[i]=max(0,a[i]-tag[id]);
        if(L<=i&&i<=R)a[i]=max(0,a[i]-x);
        if(a[i]<lp[id])go[i]=i,len[i]=0;else go[i]=go[a[i]],len[i]=len[a[i]]+1,fin[id]=false;
    }
    tag[id]=0;
}
#define fa(x) max(a[x]-tag[BLK[x]],0)
int chain(int x){
    if(x==0)return dep[x]=0;
    dep[go[x]]=chain(fa(go[x]))+1;
    if(!go[x])dep[go[x]]=0;
    return dep[x]=dep[go[x]]+len[x];
}
int read(){
    int x=0;
    char c=getchar();
    while(c>'9'||c<'0')c=getchar();
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x;
}
void modify(){
    int L=read()-1,R=read()-1,x=read();
    for(int i=BLK[L];i<=BLK[R];i++)rebuild(i,L,R,x);
}
bool lab[100100];
void LCA(){
//  printf("BEF:%d\n",dep[0]);
    int x=read()-1,y=read()-1;
    chain(x),chain(y);
//  printf("AFT:%d\n",dep[0]);
    while(go[x]!=go[y]){
        if(dep[go[x]]<dep[go[y]])swap(x,y);
        x=fa(go[x]);
    }
    lab[0]=true;
    for(int i=x;i&&BLK[i]==BLK[x];i=fa(i))lab[i]=true;
    for(int i=y;BLK[i]==BLK[y];i=fa(i))if(lab[i]){printf("%d\n",i+1);break;}
    for(int i=x;i&&BLK[i]==BLK[x];i=fa(i))lab[i]=false;
}
int main(){
//  freopen("I.in","r",stdin);
    n=read(),m=read(),a[0]=-1;
    for(int i=1;i<n;i++)a[i]=read()-1,BLK[i]=i/BBB;
    lp[num=BLK[n]=BLK[n-1]+1]=n;for(int i=0;i<num;i++)lp[i]=i*BBB;
    for(int i=0;i<num;i++)rebuild(i,-1,-1,0);
    for(int i=1;i<=m;i++)if(read()==1)modify();else LCA();
    return 0;
}

XXXIII.[APIO2019]路灯

实际上本来是在刷CDQ分治的题来着的，但是CDQ分治是众所周知地抽象，所以在碰到三维数点问题时，除非卡空间，否则一律请选择树套树……

我们可以用 set 来维护连通性。显然，若 [l,r] 这一段的路灯全亮，则所有 a,b\in[l,r+1] 都是合法的。

考虑差分。当一段 [l,r] 初次联通，就矩形加 T-t，其中 T 是总时间，t 是当前时间；当其初次不连通，就矩形减 T-t。

维护联通与否可以使用珂朵莉树，或者说，set 套 pair。

明显，这是带时间轴矩形加问题，是三维数点问题，鉴于CDQ太难写，我选择BIT套权值线段树。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,rt[300100],cnt;
#define mid ((l+r)>>1)
struct node{int lson,rson,tag;}seg[20010000];
void modify(int &x,int l,int r,int L,int R,int val){
    if(l>R||r<L)return;
    if(!x)x=++cnt;
    if(L<=l&&r<=R)seg[x].tag+=val;
    else modify(seg[x].lson,l,mid,L,R,val),modify(seg[x].rson,mid+1,r,L,R,val);
}
int query(int x,int l,int r,int P){
    if(l>P||r<P||!x)return 0;
    return seg[x].tag+query(seg[x].lson,l,mid,P)+query(seg[x].rson,mid+1,r,P);
}
void ADD(int x,int L,int R,int val){while(x<=n)modify(rt[x],1,n,L,R,val),x+=x&-x;}
int SUM(int x,int P){int ret=0;while(x)ret+=query(rt[x],1,n,P),x-=x&-x;return ret;}
void ADD(int l,int r,int val){ADD(l,l,r,val),ADD(r+1,l,r,-val);}
set<pair<int,int> >s;
char str[300100],rts[10];
int main(){
    scanf("%d%d",&n,&m),scanf("%s",str+1);
    for(int i=1,j=1;i<=n;i=j){
        while(j<=n&&str[i]==str[j])j++;
        if(str[i]=='1')s.insert(make_pair(i,j-1)),ADD(i,j-1,m);
    }
    for(int i=1,a,b;i<=m;i++){
        scanf("%s%d",rts,&a);
        if(rts[0]=='t'){
            if(str[a]=='1'){
                auto it=--s.upper_bound(make_pair(a,0x3f3f3f3f));
                int L=it->first,R=it->second;s.erase(it);
                ADD(L,R,i-m);
                if(L!=a)ADD(L,a-1,m-i),s.insert(make_pair(L,a-1));
                if(R!=a)ADD(a+1,R,m-i),s.insert(make_pair(a+1,R));
            }else{
                auto it=s.lower_bound(make_pair(a,0x3f3f3f3f));
                int L=a,R=a;
                if(it!=s.end()&&it->first==a+1)ADD(it->first,it->second,i-m),R=it->second,it=s.erase(it);
                if(it!=s.begin()&&(--it)->second==a-1)ADD(it->first,it->second,i-m),L=it->first,s.erase(it);
                ADD(L,R,m-i),s.insert(make_pair(L,R)); 
            }
//          for(auto i:s)printf("(%d %d)",i.first,i.second);puts("");
            str[a]^=1;
//          printf("%s\n",str+1);
        }else{
            scanf("%d",&b),b--;
            int ret=SUM(a,b);
            auto it=s.upper_bound(make_pair(a,0x3f3f3f3f));
            if(it!=s.begin()){
                --it;
                if(it->first<=a&&it->second>=b)ret+=i-m;
            }
            printf("%d\n",ret);
        }
    }
    return 0;
}

XXXIV.[九省联考2018]IIIDX

首先，一个非常naive的想法是，建出通关的树出来，然后dfs它，在访问到一个节点时，将现有最小的值赋给它，然后从大到小遍历每个子节点。

这个算法会被 d 相同的情形叉掉，因为它可以构造出这样一组数据：若某个节点的子树为 1，且它的兄长（指与它有同一父亲，且权值小于它的最大节点）的子树不为 1，且它的值和兄长的值相同。这时，我们可以掏出兄长的一个儿子，将其与该节点交换，并发现树仍然合法，但是字典序变大了。

于是我们开始思考这个问题的本质。

我们发现，用任意一组点集覆盖任意一棵子树，都能保证产生一组解。于是我们萌生了一个念头，能不能从小到大确定每个数的值，且使得剩余的数存在一种合法解？显然这种方法是一定正确的。

我们发现，假如一个点 x 的子树大小是 sz_x，且赋值为 b_i，则其子树中每个点的权值都 \geq b_i。这就意味着，对于 x 的子树，我们需要恰好 sz_x 个 \geq b_i 的节点来填满这棵子树。并且，依照我们上面的发现，这是充要条件。

于是问题转换为找到最大的 b_i 使得存在上述点集。

我们考虑用一棵线段树维护，线段树上每个下标 u 存了 \geq u 的尚未被动用的权值数。在确定一个点的权值为 b_i 后，我们需要对于 \leq b_i 的所有位置全都减去 sz_i，因为这其中每个位置都确定可用的权值减少了 sz_i。但是这并不意味着 >b_i 的权值数就不会变化，因为谁又知道子树中到底选了哪些数呢？

因此，在确定一个 b_i 时，我们不能简单地找到最大的权值数 \geq sz_i 的下标，而应找到对于所有 v\leq u，都有 v 的权值数 \geq sz_i 的最大 u。这是很显然的。

而这是线段树二分的常规操作。随便写写就行了。

需要注意的是，确定 b_i 时的操作的本质是预订，这就意味着当操作真正进行到儿子时，需要把父亲预订的那些位置给退回，同时注意一个父亲只能被退回一次。

时间复杂度 O(n\log n)。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,fa[500100],sz[500100],a[500100],b[500100];
double k;
vector<int>v;
#define lson x<<1
#define rson x<<1|1
#define mid ((l+r)>>1)
struct SegTree{int tag,mn;}seg[2001000];
void pushup(int x){seg[x].mn=min(seg[lson].mn,seg[rson].mn);}
void ADD(int x,int y){seg[x].mn+=y,seg[x].tag+=y;}
void pushdown(int x){ADD(lson,seg[x].tag),ADD(rson,seg[x].tag),seg[x].tag=0;}
void modify(int x,int l,int r,int P,int val){
    if(l>P)return;
    if(r<=P){ADD(x,val);return;}
    pushdown(x),modify(lson,l,mid,P,val),modify(rson,mid+1,r,P,val),pushup(x);
}
int innersearch(int x,int l,int r,int val){
    if(l==r)return seg[x].mn>=val?l:l-1;
    pushdown(x);
    if(seg[lson].mn>=val)return innersearch(rson,mid+1,r,val);
    else return innersearch(lson,l,mid,val);
}
int outersearch(int x,int l,int r,int P,int val){
//  printf("%d[%d,%d]:%d,%d\n",x,l,r,P,val);
    if(r<P)return -1;
    if(l>=P){
//      printf("[%d,%d]:%d %d\n",l,r,val,seg[x].mn);
        if(seg[x].mn>=val)return -1;
        return innersearch(x,l,r,val);
    }
    pushdown(x);
    int tmp=outersearch(lson,l,mid,P,val);
    if(tmp!=-1)return tmp;
    return outersearch(rson,mid+1,r,P,val);
}
bool vis[500100];
void iterate(int x,int l,int r){
    if(l==r)printf("%d ",seg[x].mn);
    else pushdown(x),iterate(lson,l,mid),iterate(rson,mid+1,r);
}
int main(){
    scanf("%d%lf",&n,&k);
    for(int i=n,x;i;i--)sz[fa[i]=i/k]+=++sz[i],scanf("%d",&a[i]),v.push_back(a[i]);
    sort(v.begin(),v.end()),v.resize(m=unique(v.begin(),v.end())-v.begin());
    for(int i=1;i<=n;i++)a[i]=lower_bound(v.begin(),v.end(),a[i])-v.begin()+1,modify(1,1,m,a[i],1);
//  for(int i=1;i<=n;i++)printf("%d %d\n",i,fa[i]);
//  for(int i=1;i<=n;i++)printf("%d ",sz[i]);puts("");
//  iterate(1,1,m);puts("");
    vis[0]=true,b[0]=1;
    for(int i=1;i<=n;i++){
        if(!vis[fa[i]])modify(1,1,m,b[fa[i]],sz[fa[i]]-1),vis[fa[i]]=true;
//      puts("");
//      iterate(1,1,m);puts("");
        b[i]=outersearch(1,1,m,b[fa[i]],sz[i]);
        if(b[i]==-1)b[i]=m;
//      printf("%d:%d\n",sz[i],b[i]);
        modify(1,1,m,b[i],-sz[i]);
//      iterate(1,1,m);puts("");
    }
    for(int i=1;i<=n;i++)printf("%d ",v[b[i]-1]);
    return 0;
}

XXXV.CF36E Two Paths

为什么这题会被归到数据结构博客里呢？因为我的代码使用了大剂量的 STL。

我吹爆 list 有没有！再也不手写链表了（并不），但是在欧拉路问题上真的贼好用！

首先，覆盖所有边恰一次，妥妥的欧拉路模型。

然后就先考虑如何判无解了。怎样无解呢？

1. 有少于 2 条边。（如果不是样例给了，大概很难注意到……）

2. 有超过 2 个连通块。

3. 仅有一个连通块，且连通块中奇点数大于 4。

4. 有两个连通块，且其中某一个块中奇点数大于 2。

那么，是否所有条件都满足，就一定有解呢？

是的。

假如从欧拉路的方向考虑，就会非常麻烦，因为你找出的欧拉路删去后可能使得这张图分成许多不连通的图。

因此，这里有一个很好的思路：在两个奇点间连边，这样就会转换为欧拉回路，然后在欧拉回路上断去新加的边就行了。

具体而言，对于两个连通块的情形，显然上述结论正确，因为每个连通块都必然符合条件。

然后，对于仅有一个连通块的情形，其中可能有 0 个，2 个或是 4 个奇点。