杂题记录

· · 闲话

前言

主要记录一些摸鱼是的所思所想？？？大概吧，不管他，随便写写，如果有错别字可以默认是笔者文化素养太低了，可以在评论中指出，谢谢。

当然可能会记录摸鱼时看/写的题。

DS 专场

记录一些 DS，可以常回来看看。

P4119 [Ynoi2018] 未来日记

注：默认值域和序列长度均为 n，B 表示块长。

对序列和值域分别分块，然后对序列的每个块i记录：cnt[val][i],pos[v][i] 分别表示：

  1. 序列前i个块中在值域 val 这个块中的出现元素个数之和

  2. 序列前i个块中出现的 v 的次数之和

若只考虑查询，对于序列的散块也需要处理出类似 cnt，pos一样的数组， 对于为 Scnt[val ]和 Spos[v]，其意义为：

  1. 查询的所有散块中在值域val这个块中出现的元素个数之和

  2. 查询的所有散块中v的出现次数之和

那么查询是先枚举值域的块，即先固定其值域在那个块中，即找到最小的 val 满足 （定义 b 为询问所涉及的整块构成的集合，k 的意义同题目）：

\sum_{j=1}^{val}(Scnt[j]+cnt[j][b_{last}]-cnt[j][b_{beg}-1])\geq k

然后在这个块中枚举具体的值，知道找到答案，即找到最小的 v 满足：

ans=\sum_{j=1}^{val-1}(Scnt[j]+cnt[j][b_{last}]-cnt[j][b_{beg}-1])\\ ans+\sum_{j=1}^v(Spos[j]+pos[j][b_{last}]-pos[j][b_{beg}-1])\geq k

询问时预处理复杂度是 O(B) 的，然后求 val 时要遍历 O(\frac{n}{B}) 个块，求 v 时也是遍历 O(B) 个值，所以复杂度是 O(B+\frac nB)。

对于修改操作：

遍历每个块，每个块还要存并查集，然后对于每个修改区间的整块就并查集合并，并维护 cnt,pos，对于散块就暴力重构，由于是前缀和，所以要跑完这 O(\frac{n}{B}) 个块，每个整块 O(1) 维护，对于散块则 O(B) 维护，所以修改复杂度是 O(B+\frac{n}{B})。

由此总时间复杂度是 O(m(B+\frac nB))，对于空间复杂度，每个序列块一个并查集数组，以及 cnt,pos，所以空间复杂度也是 O(\frac nB(n+\frac nB+n)) 的。 ::::info[code]

#include <bits/stdc++.h>
#define pii pair<int,int>
#define ll long long
#define mk make_pair
#define reaD read
#define raed read
#define haed head
#define cotu cout
#define se second
#define fi first
#define itn int
using namespace std;
bool Mst;
const int Max=1e5+10;
const int mod=998244353;
const int inf=1e9+10;

inline int read(){
    int x;
    cin>> x;
    return x;
}

const int Len=400;
const int B=250;
const int LenB=400;
const int BB=250;

int a[Max],n,m;

namespace valBlock{
    int belVal[Max];

    void InitVal(){
        for(int i=1;i<=B;++i){
            int l=Len*(i-1)+1;
            int r=Len*i;
            for(int j=l;j<=r;++j)belVal[j]=i;
        }
    }

}

using namespace valBlock;

namespace posBlock{

    int bel[Max];
    int fa[Max],siz[Max],val[Max];
    struct Block{
        int pos[Max],vis[Max];
        int l,r,tm;
    }b[BB+1];
    int FindFa(int x){
        return x==fa[x]?x:fa[x]=FindFa(fa[x]);
    }

    int merge(int x,int y,int va){
        x=FindFa(x);
        y=FindFa(y);
        if(x==y)return x;
        if(siz[x]>siz[y])swap(x,y);
        fa[x]=y;
        siz[y]+=siz[x];
        val[y]=va;
        return y;
    }

    void pushdown(int now){
        for(int i=b[now].l;i<=b[now].r;++i){
            a[i]=val[FindFa(i)];
        }
    }
    void pushup(int now){
        ++b[now].tm;
        for(int i=b[now].l;i<=b[now].r;++i){
            fa[i]=i;val[i]=a[i];
            siz[i]=1;
            b[now].pos[a[i]]=((b[now].vis[a[i]]==b[now].tm)?merge(b[now].pos[a[i]],i,a[i]):(b[now].vis[a[i]]=b[now].tm,i));
        }
    }
    int cnt[BB+1][B+1],pos[BB+1][Max];
    int Num;

    void Init(int n){
        Num=(n-1)/LenB+1;
        for(int i=1;i<=Num;++i){
            b[i].l=LenB*(i-1)+1;
            b[i].r=LenB*i;
        }
        b[Num].r=n;
        for(int i=1;i<=Num;++i){
            for(int j=b[i].l;j<=b[i].r;++j){
                bel[j]=i;
                cnt[i][belVal[a[j]]]++;
                pos[i][a[j]]++;
            }
        }
        for(int i=1;i<=Num;++i){
            for(int j=1;j<=B;++j){
                cnt[i][j]=cnt[i-1][j]+cnt[i][j];
            }
            for(int j=1;j<=1e5;++j){
                pos[i][j]=pos[i-1][j]+pos[i][j];
            }
            pushup(i);
        }
    }

    void Update(int l,int r,int x,int y){
        if(x==y)return;
        int st=bel[l],ed=bel[r];
        if(st==ed){
            pushdown(st);
            int res=0;
            if((b[st].vis[x]==b[st].tm)){pushdown(st);for(int i=l;i<=r;++i)if(a[i]==x){++res,a[i]=y;}pushup(st);}
            if(!res)return;
            for(int i=st;i<=Num;++i){
                cnt[i][belVal[x]]-=res;
                cnt[i][belVal[y]]+=res;
                pos[i][x]-=res;
                pos[i][y]+=res;
            }
        }else{
            int res=0;
            int u=pos[st][x];
            if((b[st].vis[x]==b[st].tm)){
                pushdown(st);
                for(int i=l;i<=b[st].r;++i){
                    if(a[i]==x){++res,a[i]=y;}
                }
                cnt[st][belVal[x]]-=res;
                cnt[st][belVal[y]]+=res;
                pos[st][x]-=res;
                pos[st][y]+=res;
                pushup(st);
            }
            for(int i=st+1;i<ed;++i){
                res+=pos[i][x]-u;//pos[i-1][x];
                u=pos[i][x];
                cnt[i][belVal[x]]-=res;
                cnt[i][belVal[y]]+=res;
                pos[i][x]-=res;
                pos[i][y]+=res;
                if((b[i].vis[x]!=b[i].tm)){
                    continue;
                }
                if((b[i].vis[y]!=b[i].tm)){
                    b[i].vis[y]=b[i].tm;
                    b[i].vis[x]=-1;
                    b[i].pos[y]=b[i].pos[x];
                    b[i].pos[x]=0;
                    val[b[i].pos[y]]=y;
                }else{
                    b[i].pos[y]=merge(b[i].pos[y],b[i].pos[x],y);
                    b[i].vis[x]=-1;
                    val[b[i].pos[y]]=y;
                }
            }
            if((b[ed].vis[x]==b[ed].tm)){
                pushdown(ed);
                for(int i=b[ed].l;i<=r;++i)if(a[i]==x){++res,a[i]=y;}
                pushup(ed);
            }
            if(!res)return;
            for(int i=ed;i<=Num;++i){
                cnt[i][belVal[x]]-=res;
                cnt[i][belVal[y]]+=res;
                pos[i][x]-=res;
                pos[i][y]+=res;
            }
        }
    }

    int Cnt[B+1],Pos[Max],visCnt[B+1],visPos[Max],ti;

    int Work1(int k){
        int i;
        for(i=1;i<=B;++i){
            if(visCnt[i]!=ti)Cnt[i]=0;
            if(k<=Cnt[i])break;
            k-=Cnt[i];
        }
        int l=Len*(i-1)+1;
        int r=Len*i;
        for(int i=l;i<=r;++i){
            if(visPos[i]!=ti)Pos[i]=0;
            if(k<=Pos[i])return i;
            k-=Pos[i];
        }
        return -inf;
    }

    int GetCnt(int l,int r,int i){
        if(l>r)return 0;
        return cnt[r][i]-cnt[l-1][i];
    }

    int GetPos(int l,int r,int i){
        if(l>r)return 0;
        return pos[r][i]-pos[l-1][i];
    }   

    int Work2(int l,int r,int k){
        int i;
        for(i=1;i<=B;++i){
            if(visCnt[i]!=ti)Cnt[i]=0;
            if(k<=Cnt[i]+GetCnt(l,r,i))break;
            k-=Cnt[i]+GetCnt(l,r,i);
        }
        int L=Len*(i-1)+1;
        int R=Len*i;
        for(int i=L;i<=R;++i){
            if(visPos[i]!=ti)Pos[i]=0;
            if(k<=Pos[i]+GetPos(l,r,i))return i;
            k-=Pos[i]+GetPos(l,r,i);
        }
        return -inf;
    }

    int Query(int l,int r,int k){
        int st=bel[l],ed=bel[r];
        if(st==ed){
            for(int i=l;i<=r;++i){
                a[i]=val[FindFa(i)];
                (visPos[a[i]]!=ti)?(Pos[a[i]]=1,visPos[a[i]]=ti):(Pos[a[i]]++);
                (visCnt[belVal[a[i]]]!=ti)?(Cnt[belVal[a[i]]]=1,visCnt[belVal[a[i]]]=ti):(Cnt[belVal[a[i]]]++);
            }
            return Work1(k);
        }else{
            for(int i=l;i<=b[st].r;++i){
                a[i]=val[FindFa(i)];
                (visPos[a[i]]!=ti)?(Pos[a[i]]=1,visPos[a[i]]=ti):(Pos[a[i]]++);
                (visCnt[belVal[a[i]]]!=ti)?(Cnt[belVal[a[i]]]=1,visCnt[belVal[a[i]]]=ti):(Cnt[belVal[a[i]]]++);
            }
            for(int i=b[ed].l;i<=r;++i){
                a[i]=val[FindFa(i)];
                (visPos[a[i]]!=ti)?(Pos[a[i]]=1,visPos[a[i]]=ti):(Pos[a[i]]++);
                (visCnt[belVal[a[i]]]!=ti)?(Cnt[belVal[a[i]]]=1,visCnt[belVal[a[i]]]=ti):(Cnt[belVal[a[i]]]++);
            }
            return Work2(st+1,ed-1,k);
        }
    }

}
using namespace posBlock;

bool Med;
signed main(){
    n=read();
    m=read();
    for(int i=1;i<=n;++i)a[i]=read();
    InitVal();
    Init(n);
    for(int i=1;i<=m;++i){
        int opt,l,r,x,y;
        opt=read();
        l=read();
        r=read();
        x=raed();
        ti=i;
        if(opt==1)y=raed(),Update(l,r,x,y);
        else cout << Query(l,r,x) << "\n";
    }

    cerr<< "Time: "<<clock()/1000.0 << "s\n";
    cerr<< "Memory: " << (&Mst-&Med)/1000000.0 << "MB\n";
    return 0;
}
/*

*/

::::

P4278 带插入区间K小值

好像类似 P4119 [Ynoi2018] 未来日记，块套块，只不过序列是一个块状链表？

::::info[code]

#include <bits/stdc++.h>
#define pii pair<int,int>
#define ll long long
#define mk make_pair
#define reaD read
#define raed read
#define haed head
#define cotu cout
#define se second
#define fi first
#define itn int
using namespace std;
bool Mst;
const int Max=7e4+10;
const int mod=998244353;
const int inf=1e9+10;

inline int read(){
    int x;
    cin>> x;
    return x;
}

const int Len=350;
const int B=200;
const int LenB=350;

int a[Max],n,m;

namespace valBlock{
    int belVal[Max];

    void InitVal(){
        for(int i=1;i<=B;++i){
            int l=Len*(i-1)+1;
            int r=Len*i;
            if(i==B)r=7e4+1;
            for(int j=l;j<=r;++j)belVal[j]=i;
        }
    }

}

using namespace valBlock;

namespace posBlock{

    struct Block{
        Block *ne;
        vector<int>d;
        int pos[Max],cnt[B+2];
        Block(){
            ne=NULL;
            d.clear();
        }
        void Ins(int x,int pos){d.insert(d.begin()+pos,x);}//插入的元素在pos处 
        void resize(int len){d.resize(len);}
        void push(int x){d.push_back(x);}
        int siz(){return d.size();}
        void clear(){d.clear();}
    }*h,*r,*z,*p,*q;

    void Insert(int pos,int x){
        for(r=h;r->ne!=NULL;r=r->ne){
            if(pos<=r->siz())break;
            pos-=r->siz();
        }
        r->Ins(x,pos-1);
        for(z=r;z!=NULL;z=z->ne){
            z->pos[x]++;
            z->cnt[belVal[x]]++;    
        }
        if(r->siz()>=(LenB<<1)){
            Block *p=new Block;
            for(int i=1;i<7e4+2;++i)p->pos[i]=r->pos[i];
            for(int i=1;i<=B;++i)p->cnt[i]=r->cnt[i];
            for(int i=LenB;i<r->siz();++i){
                p->push(r->d[i]);
                r->pos[r->d[i]]--;
                r->cnt[belVal[r->d[i]]]--;
            }
            r->resize(LenB);
            p->ne=r->ne;r->ne=p;
        }
    }

    int Pos[Max],Cnt[B+1],visPos[Max],visCnt[B+1],ti;
    int P,Z;
    int GetPos(int i) {
        if(P<=Z)return 0;
        return p->pos[i]-z->pos[i];
    }

    int GetCnt(int i){
        if(P<=Z)return 0;
        return p->cnt[i]-z->cnt[i];
    }

    int Work(int k){
        int i;
        for(i=1;i<=B;++i){
            if(visCnt[i]!=ti)Cnt[i]=0;
            if(k<=Cnt[i]+GetCnt(i))break;
            k-=Cnt[i]+GetCnt(i);
        }
        int L=Len*(i-1)+1;
        int R=Len*i;
        if(i==B)R=7e4+1;
        for(int i=L;i<=R;++i){
            if(visPos[i]!=ti)Pos[i]=0;
            if(k<=Pos[i]+GetPos(i))return i;
            k-=Pos[i]+GetPos(i);
        }
        return -inf;
    }

    int Query(int L,int R,int k){
        z=h;
        Z=0;
        for(r=h;r!=NULL;r=r->ne){
            ++Z;
            if(L<=r->siz())break;
            L-=r->siz();
        }
        z=r;
        q=r;
        p=h;
        P=0;
        for(r=h;r!=NULL;r=r->ne){
            if(R<=r->siz())break;
            ++P;
            p=r;
            R-=r->siz();
        }
        if(q!=r){
            for(int i=L-1;i<q->siz();++i){
                int p=q->d[i];
                (visPos[p]!=ti)?(Pos[p]=1,visPos[p]=ti):(Pos[p]++);
                (visCnt[belVal[p]]!=ti)?(Cnt[belVal[p]]=1,visCnt[belVal[p]]=ti):(Cnt[belVal[p]]++);
            }
            for(int i=0;i<R;++i){
                int p=r->d[i];
                (visPos[p]!=ti)?(Pos[p]=1,visPos[p]=ti):(Pos[p]++);
                (visCnt[belVal[p]]!=ti)?(Cnt[belVal[p]]=1,visCnt[belVal[p]]=ti):(Cnt[belVal[p]]++); 
            }
        }else{
            for(int i=L-1;i<R;++i){
                int p=r->d[i];
                (visPos[p]!=ti)?(Pos[p]=1,visPos[p]=ti):(Pos[p]++);
                (visCnt[belVal[p]]!=ti)?(Cnt[belVal[p]]=1,visCnt[belVal[p]]=ti):(Cnt[belVal[p]]++); 
            }
        }
        return Work(k);
    }

    void Modify(int pos,int x){
        for(r=h;r!=NULL;r=r->ne){
            if(pos<=r->siz())break;
            pos-=r->siz();
        }
        int z=r->d[pos-1];
        r->d[pos-1]=x;
        for(;r!=NULL;r=r->ne){
            r->pos[z]--;
            r->pos[x]++;
            r->cnt[belVal[z]]--;
            r->cnt[belVal[x]]++;
        }
    }

}

using namespace posBlock;

int last=0;

bool Med;
signed main(){
    n=read();
    InitVal();
    h=new Block;
    for(int i=1;i<=n;++i){
        a[i]=read()+1;
        Insert(i,a[i]);
    }
    m=read();
    for(int i=1;i<=m;++i){
        char opt;
        cin>> opt;
        ti=i;
        int x,y,val;
        x=read()^last;
        y=read()^last;
        if(opt=='Q'){
            val=(read()^last);
            cout << (last=Query(x,y,val)-1) << "\n";
        }
        if(opt=='M'){
            y+=1;
            Modify(x,y);
        }
        if(opt=='I'){
            y+=1;
            Insert(x,y);
        }
    }

    cerr<< "Time: "<<clock()/1000.0 << "s\n";
    cerr<< "Memory: " << (&Mst-&Med)/1000000.0 << "MB\n";
    return 0;
}
/*

*/

::::

P4688 [Ynoi2016] 掉进兔子洞

首先考虑如果用 bitset 来维护，我们只能求出有多少种重复元素，然后我们要求得是每种元素的最小出现次数。我们那么我们考虑让每一个元素（即使是相同的）在 bitset 种都有一个位置，那么我们可以将每个元素映射成小于等于他的元素个数 p_i 然后每次加入一个元素时将 p_i-cnt_{p} 的位置变成 1 即可。现在我们求出三个区间的 bitset 之后应该如何快速统计答案呢？原来是我看错题了呀，是求个数和就秒了。但是我们好像开不起 10^5\times 10^5 的 bitset，考虑将询问分组查询即可。 ::::info[code]

#include <bits/stdc++.h>
#define pii pair<int,int>
#define pb emplace_back
#define ll long long
#define mk make_pair
#define reaD read
#define raed read
#define haed head
#define cotu cout
#define se second
#define fi first
#define itn int
//#define mid ((l+r)>>1)
//#define rs now<<1|1
//#define ls now<<1
using namespace std;
bool Mst;
const int Max=1e5+50;
const int mod=998244353;
const int inf=1e9+10;

inline int read(){
    int res=0,v=1;
    char c=getchar();
    while(c<'0'||c>'9'){v=(c=='-'?-1:1);c=getchar();}
    while(c>='0'&&c<='9'){res=(res<<3)+(res<<1)+(c^48);c=getchar();}
    return res*v;
}

bitset<100010>res[Max/3],b; 

int a[Max],num[Max],cnt[Max];
int n,m;
vector<int>ys;
#define Ys ys.begin(),ys.end() 

struct Que{
    int l,r,id;
    Que(int l=0,int r=0,int id=0):
        l(l),r(r),id(id){;}
}q[Max];
int bel[Max],ans[Max],vis[Max];
void init(int len){
    for(int i=1;i<=len;i++){
        int l=(i-1)*len+1,r=i==len?n:i*len;
        for(int j=l;j<=r;j++) bel[j]=i;
    }
}

bool cmp(Que a,Que b){
    return bel[a.l]==bel[b.l]?a.r<b.r:bel[a.l]<bel[b.l];
}

void Add(int val){cnt[val]++;b[num[val]-cnt[val]]=1;}
void Del(int val){b[num[val]-cnt[val]]=0;cnt[val]--;}

void work(int n){
    sort(q+1,q+1+n,cmp);int l=1,r=0;
    for(int i=1;i<=n;++i){
        int L=q[i].l,R=q[i].r,id=q[i].id;
        while(r<R)Add(a[++r]);
        while(r>R)Del(a[r--]);
        while(l<L)Del(a[l++]);
        while(l>L)Add(a[--l]);
        if(!vis[id]){
            ans[id]+=R-L+1;res[id]|=b;vis[id]=1;
        }else{
            ans[id]+=R-L+1;res[id]&=b;
        }
    }
    for(int i=1;i<=n/3;++i){
        ans[i]-=3*res[i].count();
        cout << ans[i] << "\n";ans[i]=0;res[i].reset();vis[i]=0;
    }
    b.reset();
}

bool Med;
signed main(){
    n=read(),m=read();
    for(int i=1;i<=n;++i)ys.pb(a[i]=read());ys.pb(-1);
    sort(Ys);ys.erase(unique(Ys),ys.end());
    for(int i=1;i<=n;++i){cnt[a[i]=lower_bound(Ys,a[i])-ys.begin()]++;}
    for(int i=1;i<=n;++i){num[i]=num[i-1]+cnt[i];cnt[i]=0;}
    int Cnt=0,res=0;init(sqrt(n));
    for(int i=1;i<=m;++i){
        ++Cnt;
        int l1,r1,l2,r2,l3,r3;
        l1=read();r1=read();
        l2=read();r2=read();
        l3=read();r3=read();
        q[++res]=Que(l1,r1,Cnt);
        q[++res]=Que(l2,r2,Cnt);
        q[++res]=Que(l3,r3,Cnt);
        if(res>=m){
            work(res);
            Cnt=res=0;
            for(int i=1;i<=n;++i)cnt[a[i]]=0;
        }
    }
    if(Cnt)work(res);

    cerr<< "Time: "<<clock()/1000.0 << "s\n";
    cerr<< "Memory: " << (&Mst-&Med)/1000000.0 << "MB\n";
    return 0;
}

::::

P5048 [Ynoi2019 模拟赛] Yuno loves sqrt technology III

强制在线区间众数，考虑分块，先预处理出任意两块之间的所有元素的众数，后面在散块特殊处理即可。

::::info[code]

#include <bits/stdc++.h>
#define pii pair<int,int>
#define pb emplace_back
#define ll long long
#define mk make_pair
#define reaD read
#define raed read
#define haed head
#define cotu cout
#define se second
#define fi first
#define itn int
//#define mid ((l+r)>>1)
//#define rs now<<1|1
//#define ls now<<1
using namespace std;
bool Mst;
const int Max=5e5+10;
const int mod=998244353;
const int inf=1e9+10;

inline int read(){
    int res=0,v=1;
    char c=getchar();
    while(c<'0'||c>'9'){v=(c=='-'?-1:1);c=getchar();}
    while(c>='0'&&c<='9'){res=(res<<3)+(res<<1)+(c^48);c=getchar();}
    return res*v;
}

const int B=710;

struct Block{
    int l,r;
}b[B];
int maxx[B][B],ed[Max],a[Max],bel[Max];
vector<int>pos[Max];

int sum[Max],id[Max];

void pre(int n){
    int pos=(n-1)/B+1;
    for(int i=1;i<=pos;++i){
        b[i].l=(i-1)*B+1;
        b[i].r=i*B;ed[b[i].r]=i;
    }
    b[pos].r=n;
    for(int i=1;i<=pos;++i){
        for(int j=b[i].l;j<=b[i].r;++j)bel[j]=i;
        int ans=0; 
        for(int j=b[i].l;j<=n;++j){
            ans=max(ans,++sum[a[j]]);
            if(ed[j])maxx[i][ed[j]]=ans;
        }
        for(int j=b[i].l;j<=n;++j){
            sum[a[j]]=0;
        }
    }
}

int Query(int l,int r){
    int st=bel[l],ed=bel[r],ans=0;
    if(st==ed){
        for(int i=l;i<=r;++i)ans=max(ans,++sum[a[i]]);
        for(int i=l;i<=r;++i)sum[a[i]]=0;
    }else{
        ans=maxx[st+1][ed-1];
        for(int i=l;i<=b[st].r;++i)while(id[i]+ans<(int)pos[a[i]].size()&&pos[a[i]][id[i]+ans]<=r)++ans;
        for(int i=b[ed].l;i<=r;++i)while(id[i]-ans>=0&&pos[a[i]][id[i]-ans]>=l)++ans;
    }
    return ans;
}

bool Med;
signed main(){
    int n,m;
    n=read();m=read();
    for(int i=1;i<=n;++i){
        a[i]=read();id[i]=pos[a[i]].size();pos[a[i]].pb(i);
    }
    pre(n);int las=0;
    for(int i=1;i<=m;++i){
        int l=read()^las,r=read()^las;
        cout << (las=Query(l,r)) << "\n";
    }

    cerr<< "Time: "<<clock()/1000.0 << "s\n";
    cerr<< "Memory: " << (&Mst-&Med)/1000000.0 << "MB\n";
    return 0;
}

::::

P5047 [Ynoi2019 模拟赛] Yuno loves sqrt technology II

首先如果直接普通莫队+树状数组复杂度是 O(n\sqrt n\log n) 的，是过不去的。因为发现移动一次指针都要查询在 [l,r] 中有多少比 r 大的数，发现这个是个可以差分的信息，考虑莫队二离。

那么现在我们有 O(n\sqrt n) 个形如在 [1,l] 的区间中，有多少个比 a_i 大的数这类询问（先只考虑指针 r 移动），我们可以考虑按照 a_i 的大小去在序列中点亮他，现在要求一个数据结构满足可以完成 O(n) 次单点修改，O(n\sqrt n) 次区间查询，可以分块。

但是我没办法把这 O(n\sqrt n) 个询问全部存下来（出题人，你****） 。那么只有考虑压缩一些类似的询问。换个思路，发现询问可以看作在 [1,r] 中比 a_r 大的减去在 [1,l] 中比 a_r 大的。前面部分可以直接预处理，操作依然可以直接值域分块处理，依然是 O(n\sqrt n)。考虑如何压缩空间，发现每次移动指针是移动一段，所以可以直接存这个，是 O(n) 级别的，每次查询直接给这个区间做贡献即可。

::::info[code]

#include <bits/stdc++.h>
#define pii pair<int,int>
#define pb emplace_back
#define ll long long
#define mk make_pair
#define reaD read
#define raed read
#define haed head
#define cotu cout
#define se second
#define fi first
#define itn int
//#define mid ((l+r)>>1)
//#define rs now<<1|1
//#define ls now<<1
using namespace std;
bool Mst;
const int Max=2e5+10;
const int mod=998244353;
const int inf=1e9+10;

inline int read(){
    int x;
    cin>> x;
    return x;
}

template <typename T>
struct TreeArray{

    vector<T>sum;
    int len;
    inline int lowbit(int x){return x&(-x);}
    void init(int n){sum.resize(n+3);sum.clear();len=n;}
    inline T Query(int x){T ans=0;while(x){ans+=sum[x],x-=lowbit(x);}return ans;}
    inline void Modify(int x,T val){while(x<=len){sum[x]+=val,x+=lowbit(x);}}
    inline T Query(int l,int r){return Query(r)-Query(l-1);}

};

namespace Bl{  //值域分块，实现二离 

    const int B=320;
    const int Mb=1e5/B+10;
    int bel[Max];

    struct Block{
        int l,r,val,Val[B+10];
    }b[Mb];
    int pos;
    void pre(int n){
        pos=(n-1)/B+1;
        for(int i=1;i<=pos;++i){
            b[i].l=(i-1)*B+1;
            b[i].r=i*B;
        }
        b[pos].r=n;
    }
    void init(){
        for(int i=1;i<=pos;++i){
            b[i].val=0;
            for(int j=b[i].l;j<=b[i].r;++j){
                b[i].Val[j-b[i].l+1]=0;
                bel[j]=i;
            }
        }
    }

    void Modify(int x){
        int now=bel[x],L=b[now].l,R=b[now].r;
        for(int i=bel[x];i<=pos;++i)b[i].val++;
        for(int i=x;i<=R;++i)++b[now].Val[i-L+1];
    }

    int Query(int l,int r){
        if(l>r)return 0;
        int st=bel[l],ed=bel[r];
        return st==ed?b[st].Val[r-b[st].l+1]-b[st].Val[l-b[st].l]:b[ed-1].val-b[st].val+b[st].Val[b[st].r-b[st].l+1]-b[st].Val[l-b[st].l]
        +b[ed].Val[r-b[ed].l+1];
    }
}

struct Que{
    int l,r,id;
    Que(int l=0,int r=0,int id=0):
        l(l),r(r),id(id){;}
}q[Max];

vector<Que>qr[Max],ql[Max];
int bel[Max],a[Max],ed[Max];
ll ans[Max],sum[Max],Sum[Max],Ans[Max];
int n,m;

void init(int len){
    int pos=(n-1)/len+1;
    for(int i=1;i<=pos;i++){
        int l=(i-1)*len+1,r=i==pos?n:i*len;
        for(int j=l;j<=r;j++) bel[j]=i;
    }
}

bool cmp(Que a,Que b){
    return (bel[a.l]^bel[b.l])?bel[a.l]<bel[b.l]:((bel[a.l]&1)?a.r<b.r:a.r>b.r);
}

ll Get(int l,int r){return sum[r]-sum[l-1];}
ll get(int l,int r){return Sum[r]-Sum[l-1];}

int cnt=0;

void work(){
    int l=1,r=0;
    ll res=0;
    for(int i=1;i<=m;++i){
        int L=q[i].l,R=q[i].r;
        if(r<R){
            ++cnt;
            Ans[cnt]=l==1?0:-1;
            ql[l-1].pb(Que(r+1,R,cnt));
            res+=Get(r+1,R);
            r=R;
        }
        if(l>L){
            ++cnt;
            Ans[cnt]=r==n?0:-1;
            res+=get(L,l-1);
            qr[r+1].pb(Que(L,l-1,cnt));
            l=L;
        }
        if(r>R){
            ++cnt;
            Ans[cnt]=l!=1;
            res-=Get(R+1,r);
            ql[l-1].pb(Que(R+1,r,cnt));
            r=R;
        }
        if(l<L){
            ++cnt;
            Ans[cnt]=r!=n;
            res-=get(l,L-1);
            qr[r+1].pb(Que(l,L-1,cnt));
            l=L;
        }
        ans[q[i].id]+=res;
        ed[i]=cnt;
    }

}

TreeArray<int>Tr;
#define Ys ys.begin(),ys.end() 

vector<int>ys;

void pre(){
    for(int i=1;i<=n;++i)ys.pb(a[i]);ys.pb(-1);
    sort(Ys),ys.erase(unique(Ys),ys.end());
    for(int i=1;i<=n;++i)a[i]=lower_bound(Ys,a[i])-ys.begin();
    Tr.init(n+10); 
    for(int i=1;i<=n;++i){
        sum[i]=sum[i-1]+Tr.Query(a[i]+1,n);
        Tr.Modify(a[i],1);  
    }
    Tr.init(n+10); 
    for(int i=n;i>=1;--i){
        Sum[i]=Tr.Query(1,a[i]-1);
        Tr.Modify(a[i],1);  
    }
    for(int i=1;i<=n;++i)Sum[i]+=Sum[i-1];
}

void Work(){
    Bl::pre(n);Bl::init();
    for(int i=1;i<=n;++i){
        Bl::Modify(a[i]);
        for(auto j:ql[i]){
            ll val=0;
            for(int k=j.l;k<=j.r;++k){
                val+=Bl::Query(a[k]+1,n);
            }
            Ans[j.id]=val*Ans[j.id];
        }
    }
    Bl::init();
    for(int i=n;i>=1;--i){
        Bl::Modify(a[i]);
        for(auto j:qr[i]){
            ll val=0;
            for(int k=j.l;k<=j.r;++k){
                val+=Bl::Query(1,a[k]-1);
            }
            Ans[j.id]=val*Ans[j.id];
        }
    }
}
const int B=320;
bool Med;
signed main(){
    n=read();m=read();
    for(int i=1;i<=n;++i)a[i]=read();
    for(int i=1;i<=m;++i){
        int l,r;l=read();r=read();
        q[i]=Que(l,r,i);
    }
    init(B);sort(q+1,q+1+m,cmp);
    pre();work();Work();
    int Res=0;
    for(int i=1;i<=n;++i){
        for(int j=ed[i-1]+1;j<=ed[i];++j)Res+=Ans[j];
        ans[q[i].id]+=Res;
    }
    for(int i=1;i<=m;++i)cotu << ans[i] << "\n";
    cerr<< "Time: "<<clock()/1000.0 << "s\n";
    cerr<< "Memory: " << (&Mst-&Med)/1000000.0 << "MB\n";
    return 0;
}
/*

*/

::::

P5355 [Ynoi2017] 由乃的玉米田

传奇莫队+阈值分治，首先莫队用 bitset 维护当前出现的元素，我们维护两个 bitset 为 a_1,a_2，每次加入一个 x 时，令 a_1[i]=1,a_2[100001-i]=1，这样对于每次加减乘操作是好处理的，具体如下：

加：a_1\&(a_2<<(100001-x))。

减：a_1\&(a_2<<x)。

乘：直接暴力枚举 i\in [1,\sqrt x] 即可。

除：考虑阈值分治，设阈值 N=\sqrt n。

如果 x\geq N，我们可以直接枚举 i\in[1,N]，然后判断即可，一次询问复杂度是 O(\sqrt n)。

如果 x<N，不用莫队，考虑枚举 x\in[1,N] 扫描整个序列，具体来说如果当前在 i 处，维护 las[k] 表示上一个 k 的出现位置，然后维护 Ans[i] 表示以 i 结尾的最小区间满足条件的区间的右端点，然后每次更新是 Ans[i]=\max(Ans[i-1],las[x\times a[i]],las[\frac{a[i]}{x}])，这样每次询问 O(1) 查询，复杂度是 O(n\sqrt n) 的。

所以总复杂度是 O(n\sqrt n+\frac{n^2}{\omega}) 的。

::::info[code]

#include <bits/stdc++.h>
#define pii pair<int,int>
#define pb emplace_back
#define int long long
#define mk make_pair
#define reaD read
#define raed read
#define haed head
#define cotu cout
#define se second
#define fi first
#define itn int
//#define mid ((l+r)>>1)
//#define rs now<<1|1
//#define ls now<<1
using namespace std;
bool Mst;
const int Max=2e5+10;
const int mod=998244353;
const int inf=1e9+10;
const int B=320;

inline int read(){
    int res=0,v=1;
    char c=getchar();
    while(c<'0'||c>'9'){v=(c=='-'?-1:1);c=getchar();}
    while(c>='0'&&c<='9'){res=(res<<3)+(res<<1)+(c^48);c=getchar();}
    return res*v;
}

const int N=1e5;

bitset<100010>a1,a2;
int a[Max];

struct Que{
    int l,r,id,opt,x;
    Que(int l=0,int r=0,int id=0,int opt=0,int x=0):
        l(l),r(r),id(id),opt(opt),x(x){;}
}q[Max];
vector<Que>b[Max];
int bel[Max],vis[Max],n,m,ans[Max];
int M;
void init(int len){
    for(int i=1;i<=len;i++){
        int l=(i-1)*len+1,r=i==len?n:i*len;
        for(int j=l;j<=r;j++) bel[j]=i;
    }
}

bool cmp(Que a,Que b){
    return bel[a.l]==bel[b.l]?a.r<b.r:bel[a.l]<bel[b.l];
}

void Add(int val){a1[val]=a2[N-val]=1,++vis[val];}
void Del(int val){--vis[val],a1[val]=a2[N-val]=vis[val]!=0;}

int Sum(int x){return (a2&(a1<<(N-x))).any();}
int Sub(int x){return (a1&(a1<<x)).any();}
int Mul(int x){
    int z=sqrt(x)+1;
    for(int i=1;i<=z;++i){
        if(x%i==0){
            if(vis[i]&&vis[x/i])return 1; 
        }
    }
    return 0;
}
int Div(int x){
    for(int i=1;i<=M;++i){
        if(i*x<=1e5){
            if(vis[i]&&vis[i*x])return 1;
        }else break;
    }
    return 0;
}

int GetAns(int id,int x){
    if(id==2)return Sum(x);
    else if(id==1)return Sub(x);
    else if(id==3)return Mul(x);
    else return Div(x);
}

void work(int m){
    init(B);sort(q+1,q+1+m,cmp);
    int l=1,r=0;
    for(int i=1;i<=m;++i){
        int L=q[i].l,R=q[i].r;
        while(r<R)Add(a[++r]);
        while(r>R)Del(a[r--]);
        while(l>L)Add(a[--l]);
        while(l<L)Del(a[l++]);
        ans[q[i].id]=GetAns(q[i].opt,q[i].x);
    }
}

int las[Max],res[Max];

bool Med;
signed main(){
    n=read();m=read();M=sqrt(n);int cnt=0;
    for(int i=1;i<=n;++i)a[i]=read();
    for(int i=1;i<=m;++i){
        int opt,l,r,x;
        opt=read();l=read();
        r=read();x=read();
        if(opt<=3)q[++cnt]=Que(l,r,i,opt,x);
        else{
            if(x>=M)q[++cnt]=Que(l,r,i,opt,x);
            else b[x].pb(Que(l,r,i,opt,x));
        }
    }
    work(cnt);
    for(int x=1;x<M;++x){
        for(int i=1;i<=N;++i)las[i]=0,res[i]=0;
        for(int i=1;i<=n;++i){
            las[a[i]]=i;
            res[i]=res[i-1];
            if(x*a[i]<=N)res[i]=max(res[i],las[x*a[i]]);
            if(a[i]%x==0)res[i]=max(res[i],las[a[i]/x]);
        }
        for(auto j:b[x]){
            ans[j.id]=res[j.r]>=j.l;
        }
    }
    for(int i=1;i<=m;++i){
        if(ans[i])cout << "yuno\n";
        else cout << "yumi\n"; 
    }
    cerr<< "Time: "<<clock()/1000.0 << "s\n";
    cerr<< "Memory: " << (&Mst-&Med)/1000000.0 << "MB\n";
    return 0;
}
/*

*/

::::

P5046 [Ynoi2019 模拟赛] Yuno loves sqrt technology I

最后答案的构成是：整块内部的贡献 + 整块对整块的贡献 + 整块对散块的贡献 + 散块对整块的贡献 + 散块内部的贡献 + 散块对散块的贡献。

直接考虑无脑做，主打一个码量大，常熟大：

  1. 整块内部的贡献：直接树状数组 + 扫描线，复杂度 O(n\log n)。
  2. 整块对整块的贡献：对于每个数（假设是第 i 个数，在第 j 个块）预处理出在第 1 到第 i-1 个块中比当前数大的数的个数，处理这个可以在每个块内预处理前缀和做到 O(n\sqrt n) 预处理，O(1) 查询。然后每个块对块内每个位置的数组相加，这样前缀和之后可以 O(1) 查询前面块对当前块的贡献。时间复杂度是 O(n\sqrt n) 预处理，O(1) 查询。
  3. 散块和整块之间的贡献：直接枚举散块的点，按照上述 2 中处理的单点的值直接 O(1) 计算。总复杂度是 O(q\sqrt n) 的。
  4. 散块内部的贡献：在做 1 的时候顺手记录第 i 个数在其所在块中前面比他大的数的个数和后面比他小的个数，然后做前缀和和后缀和，这样可以 O(n\log n) 预 处理，O(1) 查询。
  5. 散块对散块的贡献：考虑归并求，首先对每个块排序 ，然后对于两个散块分别找到其排序后的序列，归并（扫描线）求解。
  6. 特别的：若查询区间只在一个块内，及查询 [L,R]，包含他的块为 [l,r]。那么从统计贡献的角度发现其等于 [l,R] 的贡献 + [L,r] 的贡献 + [l,L-1] 与 [R+1,r] 的贡献 - [l,r] 的贡献。

综上：空间复杂度 O(n\sqrt n)，时间复杂度 O(n\sqrt n)。然后卡不过，考虑优化。

首先对整块和整块之间的贡献计算方式进行优化：设 f_{i,j} 表示 [i,j] 区间的块的答案，设 val_{x,y} 表示第 x 个块和第 y 个块的答案。那么有转移方程：f_{i,j}=f_{i+1,j}+f_{i,j-1}-f{i+1,j-1}+val_{i,j} 然后直接 O(n\sqrt n) 预处理。

同时，对处理散块对整块贡献中那个单点值进行优化：设 f_{i,j} 表示考虑前 i 个块，其中于等于 j 的有多少个，这个直接二维前缀和，后面直接差分查询，复杂度是 O(n\sqrt n) 的。

然后将块长开小就差不多了。

代码中：sum_{i,j} 表示考虑前 i 个块，其中小于等于 j 的有多少个，Pre_{i,j} 表示 [i,j] 区间的块的答案。

::::info[code]

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
#define pii pair<int,int>
#define pb emplace_back
#define ll long long
#define mk make_pair
#define se second
#define fi first
#ifdef int
#define inf (int)1e18+10
#else
#define inf (int)1e9+10
#endif
using namespace std;
bool Mst;
const int Max=1e5+10;
const int mod=998244353;
const double eps=1e-9;

inline int read(){int x;cin>> x;return x;}
const int B=150;

template <typename T>
struct TreeArray{
    T sum[Max];int len;
    inline int lowbit(int x){return x&(-x);}
    void init(int n){len=n;}
    inline T Query(int x){T ans=0;while(x){ans+=sum[x];x-=lowbit(x);}return ans;}
    inline void Modify(int x,T val){while(x<=len){sum[x]+=val;x+=lowbit(x);}}
    inline void Update(int l,int r,T val){Modify(l,val),Modify(r+1,-val);}
    inline T Query(int l,int r){if(l>r)return 0;return Query(r)-Query(l-1);}
};
TreeArray<int>tr;
const int Len=Max/B+5;
int pre[Max],suf[Max],Id[Max];
int sum[Len][Max];
ll Pre[Len][Len];
struct Block{
    int l,r,ans,len;
    pii v[B+1];
#define v(x,i) bbb[x].v[i]
#define len(x) bbb[x].len
#define ans(x) bbb[x].ans
#define lpos(x) bbb[x].l
#define rpos(x) bbb[x].r
}bbb[Max/B+5];

int a[Max],b[2][Max],cb[2],bel[Max],n,siz[Max];

ll merge(){//b[1] 接在 b[0] 后面
    int j=1;
    ll ans=0;
    for(int i=1;i<=cb[1];++i){
        while(j<=cb[0]&&b[0][j]<b[1][i])ans+=i-1,++j;
    }
    ans+=cb[1]*(cb[0]+1-j);
    return ans;
}

int All(int l,int r){
    //预处理整块答案以及每个点在块内前面比他大的个数等信息
    int ans=0,sum=0;
    for(int i=l;i<=r;++i){
        int val=tr.Query(a[i],n);ans+=val;
        pre[i]=val+((i-1>=l)?pre[i-1]:0);
        suf[i]=sum-val;tr.Modify(a[i],1);++sum;
    }
    for(int i=l;i<=r;++i)tr.Modify(a[i],-1);
    return ans;
}

void pushup(int l,int r,int id,int lim){
    int num=0;
    for(int i=l;i<=r;++i){
        sum[id][a[i]]++;
        v(id,++num)=mk(a[i],i);
    }
    for(int i=1;i<=n;++i){sum[id][i]+=sum[id][i-1];}
    for(int i=n;i>=1;--i){sum[id][i]+=sum[id-1][i];}
    ans(id)=All(l,r);len(id)=num;
    sort(bbb[id].v+1,bbb[id].v+1+num);
    for(int i=1;i<=num;++i)suf[v(id,i).se]=i-1-suf[v(id,i).se];
    for(int i=r-1;i>=l;--i)suf[i]+=suf[i+1];
}

void Get(int l,int r,int id,int pos){
    cb[pos]=0;int tmp=len(id);
    for(int i=1;i<=tmp;++i){if(v(id,i).se>=l&&v(id,i).se<=r)b[pos][++cb[pos]]=v(id,i).fi;}
}

inline int Merge(int x,int y){
    int j=1;ll ans=0;int X=len(x),Y=len(y);
    for(int i=1;i<=Y;++i){
        while(j<=X&&v(x,j).fi<v(y,i).fi)ans+=i-1,++j;
    }
    ans+=Y*(X+1-j);
    return ans;
}

void build(){
    int num=(n-1)/B+1;
    for(int i=1;i<=num;++i){
        lpos(i)=(i-1)*B+1;
        rpos(i)=i*B;
    }
    rpos(num)=n;
    for(int i=1;i<=num;++i){
        int l=lpos(i),r=rpos(i);
        pushup(l,r,i,num);
        for(int j=l;j<=r;++j)bel[j]=i;
    }
    for(int i=1;i<=num;++i){
        siz[i]=siz[i-1]+len(i);
        for(int j=i+1;j<=num;++j){
            Pre[i][j]=Merge(i,j);
        }
        Pre[i][i]=ans(i);
    }
    for(int len=2;len<=num;++len){
        for(int i=1;i+len-1<=num;++i){
            int j=i+len-1;
            Pre[i][j]=Pre[i+1][j]+Pre[i][j-1]-Pre[i+1][j-1]+Pre[i][j];
        }
    }
}

static inline ll GetAns(int pos,int l,int r){pos=a[pos];return sum[r][pos]-sum[l-1][pos];}

ll Query(int L,int R){
    int st=bel[L],ed=bel[R];
    ll Ans=0;
    if(st==ed){
        int l=lpos(st),r=rpos(st);
        Ans=pre[R]+suf[L]-ans(st);
        Get(l,L-1,st,0);Get(R+1,r,st,1);
        Ans+=merge();
    }else{
        Ans+=Pre[st+1][ed-1]+suf[L]+pre[R];int l=lpos(ed),r=rpos(st);
        for(int i=L;i<=r;++i)Ans+=GetAns(i,st+1,ed-1);int val=siz[ed-1]-siz[st];
        for(int i=l;i<=R;++i)Ans+=val-GetAns(i,st+1,ed-1);
        Get(L,r,st,0);Get(l,R,ed,1);
        Ans+=merge();
    }
    return Ans;
}

bool Med;
signed main(){
    n=read();int m=read();
    for(int i=1;i<=n;++i)a[i]=read();
    tr.init(n);build();ll lasans=0;
    for(int i=1;i<=m;++i){
        ll l,r;l=read()^lasans;r=read()^lasans;
        cout << (lasans=Query(l,r)) << '\n';
    }
//  cerr<< "Time: "<<clock()/1000.0 << "s\n";
//  cerr<< "Memory: " << (&Mst-&Med)/1000000.0 << "MB\n";
    return 0;
}
/*

*/

::::

P7408 [JOI 2021 Final] 地牢 3 / Dungeon 3

首先对于单次询问有有显然的 O(n) 贪心，即对于第 i 个点，设其后面第一个权值小于他的点 j，若 j-i\leq U，那么当前将油加到刚好到达 j，否则将油加满。

考虑 Subtask 3 （T=N+1），提示我们从右到左扫描线。考虑如何扫描线维护上述贪心。我们维护单调递增的单调栈，但发生退栈（当前价格更优）时，设当前到栈顶的距离为 l，到栈顶的下一个位置的距离为 l'，当前位置为 i。考虑刻画贡献的变化。

首先若 l'\leq U，那么对于栈顶之前的 l'-l 的贡献要全部删除。否则，栈顶的贡献将变成 (l'-U)，那么变化量为 (U-l)。于是变化量为 \max(0,(\min(l',U)-l)) 乘以栈顶位置的单价。

这样修改了之前的贡献，同时需要加上插入点的贡献：\min(l,U) 乘以单价。

这样操作变成区间加一次函数，区间加。可以使用两棵树状数组维护，一棵维护斜率，一棵维护截距。

那么现在解决了 Subtask 3，考虑推广求任意区间。假设要求区间 [l,r] 的答案 f(l,r)，那么找到距离 r 小于等于 U 的且价值最小的位置 m。注意到过了 m 的决策是一致的，那么答案等于 f(l,n+1)-f(m,n+1)+b_m\times dis(m,r)。简单维护一下 m，即可做到 O(n\log n)。

至于 U 的值域为 10^9 怎么办呢，你™不会离散化？

::::info[其他做法] 参见 鲤鱼江 的文章 记录。 :::: ::::info[code]

#include <bits/stdc++.h>
#define pii pair<int,int>
#define pb emplace_back
#define int long long
#define mk make_pair
#define se second
#define fi first
#ifdef int
#define inf (int)1e18+10
#else
#define inf (int)1e9+10
#endif
#define mid ((l+r)>>1)
#define rs now<<1|1
#define ls now<<1
using namespace std;
bool Mst;
const int Max=5e5+10;
const int mod=998244353;
const double eps=1e-9;

inline int read(){
   int res=0,v=1;
   char c=getchar();
   while(c<'0'||c>'9'){v=(c=='-'?-1:1);c=getchar();}
   while(c>='0'&&c<='9'){res=(res<<3)+(res<<1)+(c^48);c=getchar();}
   return res*v;
}
template <typename T>
struct STA{
    T sta[Max];int Top;
    void push(T x){sta[++Top]=x;}
    int empty(){return Top?0:1;}
    T top(){return sta[Top];}
    int size(){return Top;}
    void clear(){Top=0;}
    void pop(){--Top;}
};

template <typename T>
struct TreeArray{
    vector<T>sum;int len;
    inline int lowbit(int x){return x&(-x);}
    void init(int n){len=n;sum.resize(n+3);sum.clear();}
    inline T Query(int x){T ans=0;while(x){ans+=sum[x];x-=lowbit(x);}return ans;}
    inline void Modify(int x,T val){if(!x)return;while(x<=len){sum[x]+=val;x+=lowbit(x);}}
    inline void Update(int l,int r,T val){if(r<l)return;Modify(l,val),Modify(r+1,-val);}
    inline T Query(int l,int r){if(l>r)return 0;return Query(r)-Query(l-1);}
};
int a[Max],b[Max],n,m,ans[Max];
struct SGT{
    pii minn[Max<<2];int maxx[Max<<2];
    void pushup(int now){minn[now]=min(minn[ls],minn[rs]);maxx[now]=max(maxx[ls],maxx[rs]);}
    void build(int now,int l,int r){
        if(l==r){minn[now]=mk(b[l],-l);maxx[now]=a[l];return;}
        build(ls,l,mid);build(rs,mid+1,r);pushup(now);
    }
    pii Query(int now,int l,int r,int L,int R){
        if(L>R)return mk(inf,inf);
        if(L<=l&&R>=r)return minn[now];pii ans=mk(inf,inf);
        if(L<=mid)ans=min(ans,Query(ls,l,mid,L,R));
        if(R>mid)ans=min(ans,Query(rs,mid+1,r,L,R));
        return ans;
    }
    int QueryMax(int now,int l,int r,int L,int R){
        if(R<L)return 0;
        if(L<=l&&R>=r)return maxx[now];int ans=0;
        if(L<=mid)ans=max(ans,QueryMax(ls,l,mid,L,R));
        if(R>mid)ans=max(ans,QueryMax(rs,mid+1,r,L,R));
        return ans;
    }
}tr;
struct po{
    int opt,id,u;
    po(int opt=0,int id=0,int u=0):opt(opt),id(id),u(u){;}
};
struct op{
    int l,r,u;
    op(int l=0,int r=0,int u=0):l(l),r(r),u(u){;}
}c[Max];
vector<po>v[Max];STA<int>sta;
TreeArray<int>t1,t2;int N=0;
int pos[Max];vector<int>ys;
#define Ys ys.begin(),ys.end()

int Get(int u){return t1.Query(u)*ys[u]+t2.Query(u);}

void solve(){
    sta.push(n);
    for(int i=n-1;i>=1;--i){
        while(!sta.empty()&&b[sta.top()]>b[i]){
            int L=sta.top();sta.pop();int LL=sta.top();
            int l=pos[L]-pos[i],ll=pos[LL]-pos[i];
            int tmpll=lower_bound(Ys,ll)-ys.begin();
            int tmpl=lower_bound(Ys,l)-ys.begin();
            t2.Update(tmpll,N,-(ll-l)*b[L]);
            t1.Update(tmpl,tmpll-1,-b[L]);t2.Update(tmpl,tmpll-1,l*b[L]);
        }
        int l=pos[sta.top()]-pos[i];
        int tmpl=lower_bound(Ys,l)-ys.begin();
        t2.Update(tmpl,N,l*b[i]);t1.Update(1,tmpl-1,b[i]);
        for(auto x:v[i]){
            int id,u,opt;
            id=x.id,u=x.u;opt=x.opt;
            int val=Get(u);
            ans[id]+=opt*val;
        }
        sta.push(i);
    }
}

bool Med;
signed main(){
    n=read(),m=read();
    for(int i=1;i<=n;++i)a[i]=read();
    for(int i=1;i<=n;++i)b[i]=read();
    ++n;tr.build(1,1,n);
    for(int i=2;i<=n;++i)pos[i]=pos[i-1]+a[i-1];
    for(int i=1;i<=m;++i){
        int l,r,u;l=read();r=read();u=read();
        c[i]=op(l,r,u);ys.pb(u);
    }
    ys.pb(-inf+1);ys.pb(inf);ys.pb(-inf);sort(Ys);ys.erase(unique(Ys),ys.end());N=ys.size()-1;
    // N=1e5;
    t1.init(N);t2.init(N);
    for(int i=1;i<=m;++i){
        int l=c[i].l,r=c[i].r,u=c[i].u;
        int tmp=tr.QueryMax(1,1,n,l,r-1);
        if(tmp>u){
            ans[i]=-1;
            continue;
        }
        int L=max(pos[l],pos[r]-u);
        L=lower_bound(pos+1,pos+1+n,L)-pos;
        int m=-tr.Query(1,1,n,L,r).se;
        u=lower_bound(Ys,u)-ys.begin();
        v[l].pb(po(1,i,u));v[m].pb(po(-1,i,u));
        ans[i]=b[m]*(pos[r]-pos[m]);
    }
    solve();
    for(int i=1;i<=m;++i)cout << ans[i] << "\n";

    cerr<< "Time: "<<clock()/1000.0 << "s\n";
    cerr<< "Memory: " << abs(&Mst-&Med)/1000000.0 << "MB\n";
    return 0;
}
/*

*/

战斗，爽！！！ ::::

P2048 [NOI2010] 超级钢琴

:::epigraph[——鲤鱼江] 很厉害的 trick，现在才写是不是没救了（哭）。 :::

我们注意到只有一次询问，并且 k\leq 5\times 10^5，考虑将前 k 大的全部取出来。但是发现所有可能的子串数量太多了，考虑将其合并，用最优的表示，这样当我们取出最优的后将这段分裂成若干段继续操作。

具体来说，先对原序列做前缀和得到 sum，然后记三元组 (x,l,r) 表示 \max\limits_{i=l}^rsum_i-sum_{x-1}，换句话说就是以 x 为左端点的右端点在 [l,r] 中的最大区间。这个在 ST 表的加持下可以做到 O(1) 查询。

我们对于每个 x\in[1,n] 都预先维护出所有可能的以他为左端点子串 (x,l,r)，并插入一个堆里面。那么我们每次取出最优值之后会将 [l,r] 分裂成两端，在重新插入回去，可以证明，堆的大小是 O(n+k) 级别的，所有总复杂度是 O(n\log n) 的。 ::::info[code]

#include <bits/stdc++.h>
#define pii pair<int,int>
#define pb emplace_back
#define int long long
#define mk make_pair
#define se second
#define fi first
#ifdef int
#define inf (int)1e18+10
#else
#define inf (int)1e9+10
#endif
//#define mid ((l+r)>>1)
//#define rs now<<1|1
//#define ls now<<1
using namespace std;
bool Mst;
const int Max=5e5+10;
const int mod=998244353;
const double eps=1e-9;

inline int read(){
   int res=0,v=1;
   char c=getchar();
   while(c<'0'||c>'9'){v=(c=='-'?-1:1);c=getchar();}
   while(c>='0'&&c<='9'){res=(res<<3)+(res<<1)+(c^48);c=getchar();}
   return res*v;
}

int sum[Max],a[Max];

struct ST{
    int f[20][Max];int n;int a[Max];
    inline int argmax(int x,int y){return a[x]>a[y]?(x):(y);}
    inline void init(){
        for(int i=1;i<=n;++i) f[0][i]=i;
        for(int i=1;i<=__lg(n);++i){
            for(int j=1;j<=n-(1<<i)+1;++j)
                f[i][j]=argmax(f[i-1][j],f[i-1][j+(1<<(i-1))]);
        }
    }
    inline int ask(int l,int r){
        int x=__lg(r-l+1);
        return argmax(f[x][l],f[x][r-(1<<x)+1]);
    }
}s;

struct po{
    int x,l,r,t,val;
    po(int x=0,int l=0,int r=0):x(x),l(l),r(r),t(s.ask(l,r)),val(sum[s.ask(l,r)]-sum[x-1]){;}
    bool operator <(const po x)const{return val<x.val;}
};

priority_queue<po>q;

bool Med;
signed main(){

    int n=read(),k=read(),l=read(),r=read();
    for(int i=1;i<=n;++i)sum[i]=sum[i-1]+(a[i]=read());
    s.n=n;for(int i=1;i<=n;++i)s.a[i]=sum[i];s.init();
    for(int i=1;i<=n;++i){
        int L=i+l-1,R=r+i-1;
        R=min(R,n);if(L>n)break;
        q.push(po(i,L,R));
    }
    int ans=0;
    while(k){
        auto now=q.top();q.pop();
        ans+=now.val;int x=now.x;
        int a=now.l,b=now.t-1,c=now.t+1,d=now.r;
        if(a<=b)q.push(po(x,a,b));
        if(c<=d)q.push(po(x,c,d));
        --k;
    }
    cout << ans << '\n';

    cerr<< "Time: "<<clock()/1000.0 << "s\n";
    cerr<< "Memory: " << abs(&Mst-&Med)/1000000.0 << "MB\n";
    return 0;
}
/*

*/

::::

P5064 [Ynoi Easy Round 2014] 等这场战争结束之后

考虑建出操作树，就是说若当前操作是 2 操作，那么点 i 向点 x 连边，否则向点 i-1 连边，这样在树上 DFS 时只需要支持撤销操作即可。

那么对于带撤销连通块第 k 小，可以维护 f_{x,i} 表示在以 x 为根的并查集中在第 i 个块中的元素个数，这样可以 O(n\sqrt n) 合并。注意到 20 MB，所以逐块处理。

这样复杂度是 O\sqrt n\log n 的，可能要调块长，同时把 O(n\sqrt n) 次递归吃了，变成括号序列。 ::::info[code]

#include <bits/stdc++.h>
#define pii pair<int,int>
#define pb emplace_back
#define ll long long
#define mk make_pair
#define se second
#define fi first
#ifdef int
#define inf (int)1e18+10
#else
#define inf (int)1e9+10
#endif
//#define mid ((l+r)>>1)
//#define rs now<<1|1
//#define ls now<<1
using namespace std;
bool Mst;
const int Max=1e5+10;
const int mod=998244353;
const double eps=1e-9;

inline int read(){
   int res=0,v=1;
   char c=getchar();
   while(c<'0'||c>'9'){v=(c=='-'?-1:1);c=getchar();}
   while(c>='0'&&c<='9'){res=(res<<3)+(res<<1)+(c^48);c=getchar();}
   return res*v;
}
const int B=2000;
int n,m,fa[Max],dep[Max],val[Max];vector<pii>ys;vector<int>v[Max];
struct op{int opt,x,y;op(int opt=0,int x=0,int y=0):opt(opt),x(x),y(y){;}}b[Max];
int lpos[Max/B+1],rpos[Max/B+1],a[Max],bel[Max],A[Max];
struct po{
    int x,y;
    po(int x=0,int y=0):x(x),y(y){;}
};
template <typename T>
struct STA{

    T sta[Max];int Top;
    void push(T x){sta[++Top]=x;}
    int empty(){return Top?0:1;}
    T top(){return sta[Top];}
    int size(){return Top;}
    void clear(){Top=0;}
    void pop(){--Top;}
};
STA<po>sta;
int FindFa(int x){return x==fa[x]?x:FindFa(fa[x]);}
void merge(int x,int y){
    x=FindFa(x),y=FindFa(y);
    if(dep[x]>dep[y])swap(x,y);sta.push(po(x,y));
    if(x==y)return;
    dep[y]+=dep[x];fa[x]=y;val[y]+=val[x];
}

int Len;

void init(){
    int pos=Len;
    for(int i=1;i<=pos;++i){
        lpos[i]=(i-1)*B+1;
        rpos[i]=i*B;
    }
    rpos[pos]=n;
    for(int i=1;i<=pos;++i){
        for(int j=lpos[i];j<=rpos[i];++j)bel[j]=i;
    }
}

vector<int>V;

void dfs(int now){
    if(b[now].opt)V.pb(now);
    for(auto to:v[now])dfs(to);
    if(b[now].opt==1)V.pb(-1);
}

int Ans[Max];
void Back(){
    auto z=sta.top();sta.pop();
    int x=z.x,y=z.y;if(x==y)return;
    dep[y]-=dep[x];fa[y]=y;
    val[y]-=val[x];fa[x]=x;
}

void work(int id){
    for(auto z:V){
        if(z==-1){Back();continue;}
        op &x=b[z];
        int opt=x.opt;
        if(opt==1)merge(x.x,x.y);
        if(opt==3){
            int X=FindFa(x.x);
            if(x.y<=val[X]){
                for(int i=lpos[id];i<=rpos[id];++i){
                    if(FindFa(A[i])==X){
                        --x.y;
                        if(!x.y){Ans[z]=ys[i].fi;x.opt=0;break;}
                    }
                }
            }else{
                x.y-=val[X];
            }
        }
    }
}

int Opt[Max];

bool Med;
signed main(){
    n=read(),m=read();Len=(n-1)/B+1;init();
    for(int i=1;i<=n;++i)ys.pb(mk(a[i]=read(),i));
    ys.pb(mk(-inf,0));sort(ys.begin(),ys.end());int num=-1;
    for(auto x:ys)a[x.se]=++num,A[num]=x.se;
    // for(int i=1;i<=n;++i)cout << a[i] << ' ';cout << '\n';
    for(int i=1;i<=m;++i){
        int opt,x,y;Ans[i]=-1;
        opt=read();x=read();Opt[i]=opt;
        if(opt==2){v[x].pb(i);}
        else {
            v[i-1].pb(i);y=read();
            b[i]=op(opt,x,y);
        }
    }
    // for(int i=1;i<=n;++i)v[i].resize(v[i].size());
    dfs(0);
    // exit(0);
    for(int i=1;i<=Len;++i){
        sta.clear();
        for(int j=1;j<=n;++j)fa[j]=j,dep[j]=1,val[j]=(bel[a[j]]==i);
        work(i);
    }
    for(int i=1;i<=m;++i)if(Opt[i]==3)cout << Ans[i] << "\n";

    cerr<< "Time: "<<clock()/1000.0 << "s\n";
    cerr<< "Memory: " << abs(&Mst-&Med)/1000000.0 << "MB\n";
    return 0;
}
/*

*/

::::

P9990 [Ynoi Easy Round 2023] TEST_90

考虑离线扫描线，对于第 i 个数，记录其上一次出现位置为 las_i，那么加入他时，会对 [las_i+1,i] 区间中的数作为左端点的奇偶性取反，然后最后求区间历史和。考虑用矩阵维护。

构造矩阵：

\left[ \begin{matrix} num_0&num1&ans \end{matrix} \right]

三维分别表示区间 0 的个数，区间 1 的个数，以及区间历史和。

那么异或操作如下：

\left[ \begin{matrix} 0&1&0\\ 1&0&0\\ 0&0&1 \end{matrix} \right]

维护历史和的操作如下：

\left[ \begin{matrix} 1&0&0\\ 0&1&1\\ 0&0&1 \end{matrix} \right]

直接线段树维护即可。 ::::info[code]

#include <bits/stdc++.h>
#define pii pair<int,int>
#define pb push_back
#define ll long long
#define mk make_pair
#define se second
#define fi first
#ifdef int
#define inf (int)1e18+10
#else
#define inf (int)1e9+10
#endif
#define mid ((l+r)>>1)
#define rs mid<<1|1
#define ls mid<<1
using namespace std;
bool Mst;
const int Max=1e6+10;
const int mod=998244353;
const double eps=1e-9;

inline int read(){
   int res=0,v=1;
   char c=getchar();
   while(c<'0'||c>'9'){v=(c=='-'?-1:1);c=getchar();}
   while(c>='0'&&c<='9'){res=(res<<3)+(res<<1)+(c^48);c=getchar();}
   return res*v;
}

template <typename T,int N,int M>
struct Matrix{
    T a[N][M];
    void Clear(){for(int i=0;i<N;++i)for(int j=0;j<M;++j)a[i][j]=0;}
    void init(){Clear();for(int i=0;i<N;++i)a[i][i]=1;}
    T *operator[](const int b){return a[b];}
    Matrix operator *(const Matrix &t){
        Matrix z;z.Clear();
        z[0][0]+=a[0][0]*t.a[0][0];
        z[0][1]+=a[0][0]*t.a[0][1];
        z[0][2]+=a[0][0]*t.a[0][2];
        z[0][0]+=a[0][1]*t.a[1][0];
        z[0][1]+=a[0][1]*t.a[1][1];
        z[0][2]+=a[0][1]*t.a[1][2];
        z[0][0]+=a[0][2]*t.a[2][0];
        z[0][1]+=a[0][2]*t.a[2][1];
        z[0][2]+=a[0][2]*t.a[2][2];
        z[1][0]+=a[1][0]*t.a[0][0];
        z[1][1]+=a[1][0]*t.a[0][1];
        z[1][2]+=a[1][0]*t.a[0][2];
        z[1][0]+=a[1][1]*t.a[1][0];
        z[1][1]+=a[1][1]*t.a[1][1];
        z[1][2]+=a[1][1]*t.a[1][2];
        z[1][0]+=a[1][2]*t.a[2][0];
        z[1][1]+=a[1][2]*t.a[2][1];
        z[1][2]+=a[1][2]*t.a[2][2];
        z[2][0]+=a[2][0]*t.a[0][0];
        z[2][1]+=a[2][0]*t.a[0][1];
        z[2][2]+=a[2][0]*t.a[0][2];
        z[2][0]+=a[2][1]*t.a[1][0];
        z[2][1]+=a[2][1]*t.a[1][1];
        z[2][2]+=a[2][1]*t.a[1][2];
        z[2][0]+=a[2][2]*t.a[2][0];
        z[2][1]+=a[2][2]*t.a[2][1];
        z[2][2]+=a[2][2]*t.a[2][2];
        return z;
    }
    Matrix operator +(const Matrix &t){
        Matrix z;z.Clear();
        z[0][0]=a[0][0]+t.a[0][0];
        z[0][1]=a[0][1]+t.a[0][1];
        z[0][2]=a[0][2]+t.a[0][2];
        return z;
    }
    void Out(){
        for(int i=0;i<N;++i){
            for(int j=0;j<N;++j){
                cout << a[i][j] << ' ';
            }
            cout <<"\n";
        }
    }
};
typedef Matrix<int,3,3>  Mi3;
typedef Matrix<ll,1,3>  Mi2;

Mi2 operator *(Mi2 a,Mi3 b){
    Mi2 ans;ans.Clear();
    ans[0][0]=a[0][0]*b[0][0]+a[0][1]*b[1][0]+a[0][2]*b[2][0];
    ans[0][1]=a[0][0]*b[0][1]+a[0][1]*b[1][1]+a[0][2]*b[2][1];
    ans[0][2]=a[0][0]*b[0][2]+a[0][1]*b[1][2]+a[0][2]*b[2][2];
    return ans;
}

struct SGT{
    Mi3 tag;Mi2 val;int flag=0;
}tr[Max<<1];
void pushup(int now,int l,int r){tr[now].val=tr[ls].val+tr[rs].val;}
void work(int now,Mi3 &tag){
    tr[now].tag=tr[now].tag*tag;tr[now].val=tr[now].val*tag;tr[now].flag=1;
}
void pushdown(int now,int l,int r){
    if(tr[now].flag){
        work(ls,tr[now].tag);work(rs,tr[now].tag);tr[now].tag.init();tr[now].flag=0;
    }
}

void Update(int now,int l,int r,int L,int R,Mi3 &val){
    if(L<=l&&R>=r)return work(now,val);pushdown(now,l,r);
    if(L<=mid)Update(ls,l,mid,L,R,val);
    if(R>mid)Update(rs,mid+1,r,L,R,val);
    pushup(now,l,r);
}

void build(int now,int l,int r){
    tr[now].tag.init();if(l==r){tr[now].val[0][0]=1;return;}
    build(ls,l,mid);build(rs,mid+1,r);pushup(now,l,r);
}

ll Query(int now,int l,int r,int L,int R){
    if(L<=l&&R>=r)return tr[now].val[0][2];pushdown(now,l,r);
    ll ans=0;if(L<=mid)ans+=Query(ls,l,mid,L,R);
    if(R>mid)ans+=Query(rs,mid+1,r,L,R);
    return ans;
}

int a[Max],las[Max],pos[Max];
vector<pii>q[Max];ll Ans[Max];
Mi3 Xor,And;

bool Med;
signed main(){
    Xor.Clear();Xor[0][1]=Xor[1][0]=Xor[2][2]=1;
    And.Clear();And[0][0]=And[1][1]=And[1][2]=And[2][2]=1;
    int n=read();for(int i=1;i<=n;++i)a[i]=read();int m=read();
    for(int i=1;i<=n;++i){las[i]=pos[a[i]];pos[a[i]]=i;}
    for(int i=1;i<=m;++i){
        int l,r;
        l=read();r=read();
        q[r].pb(mk(l,i));
    }
    build(1,1,n);
    for(int i=1;i<=n;++i){
        Update(1,1,n,las[i]+1,i,Xor);
        Update(1,1,n,1,i,And);
        for(int j=0;j<q[i].size();++j){
            pii x=q[i][j];
            Ans[x.se]=Query(1,1,n,x.fi,i);
        }
    }
    for(int i=1;i<=m;++i)cout << Ans[i] << '\n';
    return 0;
}
/*

*/

::::

P9991 [Ynoi Easy Round 2023] TEST_107

考虑从区间中删除颜色，考虑一个颜色相邻两次出现的位置，称作 x,y，有以下三种情况可能产生贡献：

这三种贡献都可以直接扫描线，时间复杂度 O(n\log n)。 ::::info[code]

#include <bits/stdc++.h>
#define pii pair<int,int>
#define pb emplace_back
#define ll long long
#define mk make_pair
#define se second
#define fi first
#ifdef int
#define inf (int)1e18+10
#else
#define inf (int)1e9+10
#endif
#define mid ((l+r)>>1)
#define rs now<<1|1
#define ls now<<1
using namespace std;
bool Mst;
const int Max=2e6+10;
const int mod=998244353;
const double eps=1e-9;

inline int read(){
   int res=0,v=1;
   char c=getchar();
   while(c<'0'||c>'9'){v=(c=='-'?-1:1);c=getchar();}
   while(c>='0'&&c<='9'){res=(res<<3)+(res<<1)+(c^48);c=getchar();}
   return res*v;
}

inline int max(const int &x,const int &y){return x>y?x:y;}
struct SGT{
    int tag[Max<<2];
    void Update(int now,int l,int r,int L,int R,int val){
        if(L<=l&&R>=r)return tag[now]=max(tag[now],val),void();
        if(L<=mid)Update(ls,l,mid,L,R,val);
        if(R>mid)Update(rs,mid+1,r,L,R,val);
    }
    int Query(int now,int l,int r,int to){return max(tag[now],(l==r)?-inf:(to<=mid?Query(ls,l,mid,to):Query(rs,mid+1,r,to)));}
    void build(int now,int l,int r){tag[now]=-inf;if(l==r)return;build(ls,l,mid);build(rs,mid+1,r);}
}t;

template <typename T>
struct TreeArray{
    vector<T>sum;int len;
    inline int lowbit(int x){return x&(-x);}
    void init(int n){len=n;sum.resize(n+3);sum.clear();}
    inline T Query(int x){T ans=0;while(x<=len){ans=max(ans,sum[x]);x+=lowbit(x);}return ans;}
    inline void Modify(int x,T val){while(x){sum[x]=max(sum[x],val);x-=lowbit(x);}}
};
TreeArray<int>s;
int ans[Max],a[Max],pos[Max];vector<pii>v[Max],V[Max];

bool Med;
signed main(){
    int n=read(),m=read();
    for(int i=1;i<=n;++i)a[i]=read();
    for(int i=1;i<=m;++i){int x,y;x=read(),y=read();v[y].pb(mk(x,i));V[x].pb(mk(y,i));}
    for(int i=1;i<=n;++i){
        t.Update(1,1,n,pos[a[i]]+1,i,i);
        // cout << pos[a[i]]+1 << ' ' << i << "---\n";
        pos[a[i]]=i;
        for(auto x:v[i]){ans[x.se]=max(ans[x.se],t.Query(1,1,n,x.fi)-x.fi);}
    }
    s.init(n);for(int i=1;i<=n;++i)pos[a[i]]=0;
    for(int i=1;i<=n;++i){
        if(pos[a[i]])s.Modify(pos[a[i]],i-pos[a[i]]-1);
        pos[a[i]]=i;for(auto x:v[i])ans[x.se]=max(ans[x.se],s.Query(x.fi));
    }
    t.build(1,1,n);
    for(int i=1;i<=n;++i)pos[a[i]]=n+1;
    for(int i=n;i>=1;--i){
        t.Update(1,1,n,i,pos[a[i]]-1,-i);pos[a[i]]=i;
        for(auto x:V[i]){ans[x.se]=max(ans[x.se],x.fi+t.Query(1,1,n,x.fi));}
    }
    for(int i=1;i<=m;++i)cout << ans[i] << '\n';
    cerr<< "Time: "<<clock()/1000.0 << "s\n";
    cerr<< "Memory: " << abs(&Mst-&Med)/1000000.0 << "MB\n";
    return 0;
}
/*

*/

::::

P12461 [Ynoi Easy Round 2018] 星野爱

首先套路的考虑分块，但是是带权分块，我们保证每个块内的点的度数之和小于等于 B，因为度数之和是 O(n) 级别的，所以总块数是 O(\frac nB) 级别的。

考虑修改：

  1. 散块对散块：直接暴力计算贡献。
  2. 整块对区间：维护一个数组 f_{i,j} 表示若第 i 个块加 1，那么第 j 个点的相邻点会加多少。
  3. 散块对整块：和上述本质相同。

发现空间是 O(n\sqrt n) 的，逐块处理即可。

::::info[code]

#include <bits/stdc++.h>
#define pii pair<int,int>
#define pb emplace_back
#define ll unsigned long long
#define mk make_pair
#define se second
#define fi first
#ifdef int
#define inf (int)1e18+10
#else
#define inf (int)1e9+10
#endif
//#define mid ((l+r)>>1)
//#define rs now<<1|1
//#define ls now<<1
using namespace std;
bool Mst;
const int Max=4e5+10;
const int mod=998244353;
const double eps=1e-9;

inline int read(){
   int res=0,v=1;
   char c=getchar();
   while(c<'0'||c>'9'){v=(c=='-'?-1:1);c=getchar();}
   while(c>='0'&&c<='9'){res=(res<<3)+(res<<1)+(c^48);c=getchar();}
   return res*v;
}

struct Query{
    int op,l,r,v,zl,zr;
    Query(int op=0,int l=0,int r=0,int v=0):
        op(op),l(l),r(r),v(v){;}
}q[Max];
int n,m,Q,lenth,pos[Max],lpos[Max],rpos[Max],tot,ct[Max],a[Max],L[Max],R[Max],cnt;
vector < int > v[Max];ll ans[Max],val[Max],f[Max],w,now,VAL;

inline void add(int x,int y){v[x].emplace_back(y);v[y].emplace_back(x);}
inline void SetBlock(int l,int r){
    ++tot;for(int i=l;i<=r;++i) pos[i]=tot;
    lpos[tot]=l;rpos[tot]=r;
}
inline void Corner(int id){//处理散块 
    int op=q[id].op,l=q[id].l,r=q[id].r,vl=q[id].v;
    int st=pos[l],ed=pos[r];
    q[id].zl=st+(l!=lpos[st]);
    q[id].zr=ed-(r!=rpos[ed]);
    if(l==lpos[st]&&r==rpos[ed]) return ;
    if(op==1){
        if(st==ed){
            for(int i=l;i<=r;++i) for(int j=L[i];j<=R[i];++j) val[a[j]]+=vl;
        }else {
            if(l!=lpos[st]) for(int i=l;i<=rpos[st];++i) for(int j=L[i];j<=R[i];++j) val[a[j]]+=vl;
            if(r!=rpos[ed]) for(int i=lpos[ed];i<=r;++i) for(int j=L[i];j<=R[i];++j) val[a[j]]+=vl;
        } 
    }else {
        if(st==ed){
            for(int i=l;i<=r;++i) for(int j=L[i];j<=R[i];++j) ans[id]+=val[a[j]];
        }else {
            if(l!=lpos[st]) for(int i=l;i<=rpos[st];++i) for(int j=L[i];j<=R[i];++j) ans[id]+=val[a[j]];
            if(r!=rpos[ed]) for(int i=lpos[ed];i<=r;++i) for(int j=L[i];j<=R[i];++j) ans[id]+=val[a[j]];
        }
    }
}
inline void init(int id){
    for(int j=L[lpos[id]];j<=R[rpos[id]];++j) ++ct[a[j]];
    for(int i=1;i<=n;++i){
        for(int j=L[i];j<=R[i];++j) f[i]+=ct[a[j]];
        f[i]+=f[i-1];
    }
}
inline void clear(){VAL=w=0;for(int i=1;i<=n;++i) ct[i]=f[i]=val[i]=0;}
inline void Solve1(int p){//整块对区间 
    int op=q[p].op,l=q[p].l,r=q[p].r,v=q[p].v;
    if(op==1){if(l<=lpos[now]&&rpos[now]<=r) w+=v;}
    else ans[p]+=(f[r]-f[l-1])*w;
}
inline void Solve2(int p){//散块对整块 
    int op=q[p].op,l=q[p].l,r=q[p].r,v=q[p].v;
    if(op==1){
        if(q[p].zl<=q[p].zr){
            int sl=l,sr=rpos[q[p].zl-1];VAL+=(f[sr]-f[sl-1])*v;
            sl=lpos[q[p].zr+1];sr=r;VAL+=(f[sr]-f[sl-1])*v; 
        }else VAL+=(f[r]-f[l-1])*v;
    }else if(l<=lpos[now]&&rpos[now]<=r) ans[p]+=VAL;
}
inline void Deal(int id){for(int i=1;i<=Q;++i){Solve1(i);Solve2(i);}}

bool Med;
signed main(){
    n=read();m=read();Q=read();
    for(int i=1;i<=m;++i){int x,y;x=read(),y=read();add(x,y);}
    for(int i=1;i<=Q;++i){
        int opt,l,r,v=0;
        opt=read();l=read();r=read();
        if(opt==1)v=read();
        q[i]=Query(opt,l,r,v);
    }
    for(int i=1;i<=n;++i){
        L[i]=cnt+1;
        for(int j:v[i]) a[++cnt]=j;
        R[i]=cnt;
    }
    lenth=4*sqrt(m);int s=0,las=1;
    for(int i=1;i<=n;++i){//带权分块 
        int sz=v[i].size()+1;
        if(s+sz>lenth){
            s=0;
            if(las==i) SetBlock(i,i),las=i+1;
            else {SetBlock(las,i-1);las=i;--i;continue;}
        }else s+=sz;
    }
    if(las<=n) SetBlock(las,n); 
    lpos[tot+1]=n+1;for(int i=1;i<=Q;++i) Corner(i);
    for(int i=1;i<=tot;++i){now=i;init(i);Deal(i);clear();}
    for(int i=1;i<=Q;++i) if(q[i].op==2) cout<<ans[i]<<'\n';
    cerr<< "Time: "<<clock()/1000.0 << "s\n";
    cerr<< "Memory: " << abs(&Mst-&Med)/1000000.0 << "MB\n";
    return 0;
}
/*

*/

::::

P9989 [Ynoi Easy Round 2023] TEST_69

由于是取 gcd，所以每个位置只会变化 O(\log) 次，那么我们考虑找到变化的位置。

发现若对于一个区间 [l,r] 中的每个元素都有 a_i=\gcd(a_i,x)，那么有 x\equiv 0\pmod {\text{lcm}_{i=l}^r a_i}，区间 \text{lcm} 可以线段树维护，若其大于 10^{18} 直接设置成 inf 即可，时间复杂度是 O(n\log^2 n) 的。 ::::info[code]

#include <bits/stdc++.h>
#define pii pair<int,int>
#define pb emplace_back
#define ll unsigned int
#define LL long long
#define mk make_pair
#define se second
#define fi first
#define mid ((l+r)>>1)
#define rs now<<1|1
#define ls now<<1
using namespace std;
bool Mst;
const int Max=2e5+10;
const int mod=998244353;
const double eps=1e-9;

inline LL read(){
   LL res=0,v=1;
   char c=getchar();
   while(c<'0'||c>'9'){v=(c=='-'?-1:1);c=getchar();}
   while(c>='0'&&c<='9'){res=(res<<3)+(res<<1)+(c^48);c=getchar();}
   return res*v;
}

struct SGT{
    ll sum;
    LL lcm;
}tr[Max<<3];
int tot=Max<<2;
LL a[Max];
void pushup(int now){
    tr[now].lcm=min((__int128)2e18,(__int128)tr[ls].lcm*tr[rs].lcm/__gcd(tr[ls].lcm,tr[rs].lcm));
    tr[now].sum=tr[ls].sum+tr[rs].sum;
}
void build(int now,int l,int r){
    if(l==r){tr[now].sum=tr[now].lcm=a[l];return;}
    build(ls,l,mid);build(rs,mid+1,r);pushup(now);
}

void Update(int now,int l,int r,int L,int R,LL val){
    if(val%tr[now].lcm==0)return;
    if(l==r){tr[now].sum=tr[now].lcm=__gcd(val,tr[now].lcm);return;}
    if(L<=mid)Update(ls,l,mid,L,R,val);
    if(R>mid)Update(rs,mid+1,r,L,R,val);
    pushup(now);
}
ll Query(int now,int l,int r,int L,int R){
    if(L<=l&&R>=r)return tr[now].sum;ll ans=0;
    if(L<=mid)ans+=Query(ls,l,mid,L,R);
    if(R>mid)ans+=Query(rs,mid+1,r,L,R);
    return ans;
}

bool Med;
signed main(){
    int n=read(),m=read();
    for(int i=1;i<=n;++i)a[i]=read();
    build(1,1,n);
    for(int i=1;i<=m;++i){
        LL opt,l,r,x;
        opt=read();l=read();r=read();
        if(opt==1){
            x=read();Update(1,1,n,l,r,x);
        }else cout << Query(1,1,n,l,r) << "\n";
    }

    cerr<< "Time: "<<clock()/1000.0 << "s\n";
    cerr<< "Memory: " << abs(&Mst-&Med)/1000000.0 << "MB\n";
    return 0;
}

::::

P8511 [Ynoi Easy Round 2021] TEST_68

首先，求两个元素的异或最大值可以使用 01-trie 解决。发现有多数情况下的答案是全局最大值。

那么先找出一对全局最大值 x,y，那么需要特殊处理的点位于 x\to 1 或者 y\to 1 的路径上。在 dfs 时，每次暴力加入点的复杂度是对的，总复杂度是 O(n\log n) 的。 ::::info[code]

#include <bits/stdc++.h>
#define pii pair<int,int>
#define pb emplace_back
#define ll long long
#define mk make_pair
#define se second
#define fi first
#ifdef int
#define inf (int)1e18+10
#else
#define inf (int)1e9+10
#endif
//#define mid ((l+r)>>1)
//#define rs now<<1|1
//#define ls now<<1
using namespace std;
bool Mst;
const int Max=5e5+10;
const int mod=998244353;
const double eps=1e-9;

inline ll read(){
   ll res=0,v=1;
   char c=getchar();
   while(c<'0'||c>'9'){v=(c=='-'?-1:1);c=getchar();}
   while(c>='0'&&c<='9'){res=(res<<3)+(res<<1)+(c^48);c=getchar();}
   return res*v;
}

const int B=62;
struct Trie{
    int ch[2],ed;
    #define ch(x,i) tr[x].ch[i]
    #define ed(x) tr[x].ed
}tr[Max<<6];
int tot;
void Insert(ll x,int id){
    int now=0;
    for(int i=B;~i;--i){
        int to=0;
        if((x>>i)&1)to=1;
        if(!ch(now,to)){ch(now,to)=++tot;}
        now=ch(now,to);
    }
    ed(now)=id;
}

int Query(ll x){
    int now=0;
    for(int i=B;~i;--i){
        int to=1;
        if((x>>i)&1)to=0;
        if(ch(now,to))now=ch(now,to);
        else now=ch(now,!to);
    }
    return ed(now);
}

int vis[Max],fa[Max],n;
vector<int>v[Max];ll val,ans[Max],a[Max];
void clear(){for(int i=0;i<=tot;++i)ed(i)=ch(i,0)=ch(i,1)=0;tot=0;for(int i=1;i<=n;++i)vis[i]=0;}

void jump(int x,int tag=1){
    while(x){
        vis[x]=tag;x=fa[x];
    }
}

ll Val=0;

void dfs2(int now){
    Insert(a[now],now);
    int pos=Query(a[now]);
    Val=max(Val,a[pos]^a[now]);
    for(auto to:v[now]){
        if(!vis[to])dfs2(to);
    }
}

void dfs3(int now){
    ans[now]=Val;
    Insert(a[now],now);
    int pos=Query(a[now]);
    Val=max(Val,a[pos]^a[now]);
    for(auto to:v[now]){
        if(!vis[to]){
            dfs2(to);
        }
    }
    for(auto to:v[now]){
        if(vis[to])dfs3(to);
    }
}

void work(int x,int y){
    clear();jump(y,0);jump(x,1);vis[1]=0;Val=0;dfs2(1);
    for(auto to:v[1])if(vis[to])dfs3(to);
}

bool Med;
signed main(){
    n=read();
    for(int i=2;i<=n;++i){v[fa[i]=read()].pb(i);}
    for(int i=1;i<=n;++i)a[i]=read();
    val=0;pii res;
    for(int i=1;i<=n;++i){
        ll Val=0;int pos;
        Insert(a[i],i);
        pos=Query(a[i]);
        Val=a[i]^a[pos];
        if(Val>val){
            val=Val;
            res=mk(pos,i);
        }
    }
    int x=res.fi,y=res.se;
    jump(res.fi);jump(res.se);
    for(int i=2;i<=n;++i){if(!vis[i]){ans[i]=val;}}
    work(x,y);work(y,x);ans[1]=0;
    for(int i=1;i<=n;++i)cout << ans[i] << '\n';

    cerr<< "Time: "<<clock()/1000.0 << "s\n";
    cerr<< "Memory: " << abs(&Mst-&Med)/1000000.0 << "MB\n";
    return 0;
}
/*

*/

::::

P9068 [Ynoi Easy Round 2022] 超人机械 TEST_95

题意：单点修改，全局本质不同逆序对数。

用 x_i,y_i 表示 i 第一次和最后一次出现的位置，那么两个数 i>j 之间有贡献当且仅当 x_i<y_j。修改明显只影响 O(1) 个 x,y。

算上时间轴很明显是一个三维偏序的形式，离线下来直接套用 CDQ 分治可以做到 O(n\log^2 n)。

数学场

【GDSOI 2016】第一题 互补约数

法一

\begin{aligned} \sum_{i=1}^n\sum_{j|i}\gcd\left(j,\frac ij\right) &=\sum_{i=1}^n\sum_{j=1}^n \gcd(i,j)[ij\leq n]\\ &=\sum_{d=1}^nd\sum_{i=1}^n\sum_{j=1}^n[\gcd(i,j)=d][ij\leq n]\\ &=\sum_{d=1}^nd\sum_{i=1}^{\lfloor\frac nd\rfloor}\sum_{j=1}^{\lfloor\frac nd\rfloor }[\gcd(i,j)=1][ijd^2\leq n]\\ &=\sum_{d=1}^nd\sum_{i=1}^{\lfloor\frac nd\rfloor}\sum_{j=1}^{\lfloor\frac nd\rfloor }\sum_{k|i,k|j}\mu(k)[ijd^2\leq n]\\ &=\sum_{d=1}^nd\sum_{k=1}^{\lfloor\frac nd\rfloor}\mu(k)\sum_{k|i}\sum_{k|j}[ijd^2\leq n]\\ &=\sum_{d=1}^nd\sum_{k=1}^{\lfloor\frac nd\rfloor}\mu(k)\sum_{i=1}^{\lfloor\frac n{kd}\rfloor}\sum_{j=1}^{\lfloor\frac n{kd}\rfloor}[ijk^2d^2\leq n]\\ &=\sum_{t=1}^n\left(\sum_{d|t}d\mu\left(\frac td\right)\right)\sum_{i=1}^{\lfloor\frac nt\rfloor}\sum_{j=1}^{\lfloor\frac nt\rfloor}[ijt^2\leq n]\\ &=\sum_{t=1}^n\varphi(t)\sum_{i=1}^{\lfloor\frac nt\rfloor}\sum_{j=1}^{\lfloor\frac nt\rfloor}[ijt^2\leq n]\\ &=\sum_{t=1}^n\varphi(t)\sum_{i=1}^{\lfloor\frac nt\rfloor}\left\lfloor\frac {n}{it^2}\right\rfloor\\ &=\sum_{t=1}^{\sqrt n}\varphi(t)\sum_{t=1}^{\left\lfloor \frac{n}{t^2}\right\rfloor}\left\lfloor\frac {n}{it^2}\right\rfloor\\ \end{aligned}

法二

\begin{aligned} \sum_{i=1}^n\sum_{j|i}\gcd\left(j,\frac ij\right) &=\sum_{i=1}^n\sum_{j=1}^n \gcd(i,j)[ij\leq n]\\ &=\sum_{i=1}^n\sum_{j=1}^n\sum_{t|i,t|j}\varphi(t)[ij\leq n]\\ &=\sum_{t=1}^n\varphi(t)\sum_{t|i}\sum_{t|j}[ij\leq n]\\ &=\sum_{t=1}^n\varphi(t)\sum_{i=1}^{\lfloor\frac nt\rfloor}\sum_{j=1}^{\lfloor\frac nt\rfloor}[ijt^2\leq n]\\ &=\sum_{t=1}^n\varphi(t)\sum_{i=1}^{\lfloor\frac nt\rfloor}\left\lfloor\frac {n}{it^2}\right\rfloor\\ &=\sum_{t=1}^{\sqrt n}\varphi(t)\sum_{t=1}^{\left\lfloor \frac{n}{t^2}\right\rfloor}\left\lfloor\frac {n}{it^2}\right\rfloor\\ \end{aligned}

两种方法得到相同的式子，最后数论分块解决。

#include <bits/stdc++.h>
#define pii pair<int,int>
#define pb emplace_back
#define int long long
#define mk make_pair
#define se second
#define fi first
#ifdef int
#define inf (int)1e18+10
#else
#define inf (int)1e9+10
#endif
//#define mid ((l+r)>>1)
//#define rs now<<1|1
//#define ls now<<1
using namespace std;
bool Mst;
const int Max=1e6+10;
const int mod=998244353;
const double eps=1e-9;

inline int read(){
   int res=0,v=1;
   char c=getchar();
   while(c<'0'||c>'9'){v=(c=='-'?-1:1);c=getchar();}
   while(c>='0'&&c<='9'){res=(res<<3)+(res<<1)+(c^48);c=getchar();}
   return res*v;
}

int phi[Max],pr[Max],vis[Max],tot;

void pre(int n=Max-1){
    phi[1]=vis[1]=1;
    for(int i=2;i<=n;++i){
        if(!vis[i]){pr[++tot]=i;phi[i]=i-1;}
        for(int j=1;j<=tot&&i*pr[j]<=n;++j){
            vis[i*pr[j]]=1;
            if(i%pr[j]==0){
                phi[i*pr[j]]=phi[i]*pr[j];
                break;
            }
            phi[i*pr[j]]=phi[i]*(pr[j]-1);
        }
    }
}

int Get(int n){
    int ans=0,j=0;
    for(int i=1;i<=n;i=j+1){
        j=n/(n/i);ans+=(n/i)*(j-i+1);
    }
    return ans;
}

bool Med;
signed main(){
    freopen("gcd.in","r",stdin);freopen("gcd.out","w",stdout);
    pre();int n=read();int ans=0;
    for(int i=1;i*i<=n;++i){
        ans+=phi[i]*Get(n/i/i);
    }
    cout << ans << '\n';

    cerr<< "Time: "<<clock()/1000.0 << "s\n";
    cerr<< "Memory: " << abs(&Mst-&Med)/1000000.0 << "MB\n";
    return 0;
}
/*

*/