数据结构

· · 算法·理论

（~如果有的话~） 读者请先看底部说明

1.并查集

并查集是一种能够判断两个元素是否属于同一个集合的数据结构，主要有操作有：将两个集合合并；查询一个元素所在的集合。

查询：

int fid(int x){
    if(fa[x]==x) return x;
    return fa[x]=fid(fa[x]);
}

合并

void merge(int x,int y){
    x=fa[x],y=fa[y];
    if(x==y) return;
    fa[x]=y;
}

2.线段树

(1).基础

略

(2).扫描线

_1.求面积

首先将点离散化。将每一根线段用线段树上的一个点表示，线段树上的每一个点代表的线段都是右端点x减去左端点x，注意叶子节点不能产生贡献。最后按线段的高度排序，并加上in/out标签。

_2.特殊意义的扫描线

可以处理除去1\~l-1对l\~r的贡献的问题。

同样将每根线段的左右端点单独列出来，并打上in/out标签，类似于高度按照某个量排序。

_3.李超线段树

P4097

李超线段树用于解决：在平面直角坐标系中插入线段，问一个x在哪一条线段上取到最大的y。

原理：两条线段最多只有一个交点，根据这点，对一个区间，李超线段树只维护在该区间内在大多数时候y最大(表现为该线段在当前区间mid处的y比其它线段都大)的线段，而反常的时候怎么办呢？由于两条线段最多只有一个交点，反常的位置只能在左或右的一段，那么向下递归更新反常的那一段即可，直到确定每一段区间的大多数时候y最大的线段。查询时，由于是单点查询，可以O(logn)直接递归到底。由于和其它线段树不同，该线段树只维护大多数时候正确的那个答案，所以一定要递归到底，且要在每一层都取max。

代码：

#include<bits/stdc++.h>
using namespace std;
int m,ans,tot;
const int inf=1e9+7;
const double eps=1e-10;
struct o{
    int xma,xmi;
    double k,b;
    double operator ()(int x){
        if(x<=xma&&x>=xmi) return  1.0*(k*x+b);
        return -inf;
    }
}a[5000100];
struct oo{
    int tree[5000100];
    pair<double,int> ma(pair<double,int>a,pair<double,int>b ){
        if(a.first-b.first>eps) return a;
        if(b.first-a.first>eps) return b;
        return a.second<b.second?a:b;
    }
    int ls(int k){return k<<1;}
    int rs(int k){return k<<1|1;}
    void change(int k,int l,int r,int x,int y,int v){
        if(x<=l&&y>=r){
            if(!tree[k]){
                tree[k]=v;
                return;
            }
            int mid=(l+r)>>1;
            if(a[v](mid)-a[tree[k]](mid)>eps) swap(v,tree[k]);

            if(a[v](l)-a[tree[k]](l)>eps||(fabs(a[v](l)-a[tree[k]](l))<=eps&&v<tree[k])) change(ls(k),l,mid,x,y,v);
            if(a[v](r)-a[tree[k]](r)>eps||(fabs(a[v](r)-a[tree[k]](r))<=eps&&v<tree[k])) change(rs(k),mid+1,r,x,y,v);
            return;
        }
        int mid=(l+r)>>1;
        if(x<=mid) change(ls(k),l,mid,x,y,v);
        if(y>mid) change(rs(k),mid+1,r,x,y,v);
        return;
    }
    pair<double,int> ask(int k,int l,int r,int x){
        pair<double,int>res;
        if(tree[k]) res=make_pair(a[tree[k]](x),tree[k]);
        if(l==r){
            return res;
        }
        int mid=(l+r)>>1;
        if(x<=mid) res=ma(ask(ls(k),l,mid,x),res);
        else res=ma(ask(rs(k),mid+1,r,x),res);
        return res;
    }
}t;
int read(){
    char ch=getchar();int x=0,f=1;
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch<='9'&&ch>='0'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
int main(){
    m=read();
    while(m--){
        int op=read();
        if(op){
            int x0=read(),y0=read();
            int x1=read(),y1=read();
            x0=(x0+ans-1)%39989+1;
            y0=(y0+ans-1)%(1000000000)+1;
            x1=(x1+ans-1)%39989+1;
            y1=(y1+ans-1)%(1000000000)+1;
            if(x1==x0){
                ++tot;
                a[tot].xma=a[tot].xmi=x1;
                a[tot].b=max(y1,y0);
                a[tot].k=0;
            }else{
                a[++tot].xma=max(x1,x0);
                a[tot].xmi=min(x1,x0);
                a[tot].k=1.0*(y0-y1)/(x0-x1);
                a[tot].b=1.0*(1.0*y1-1.0*a[tot].k*x1);
            }
            t.change(1,1,39990,min(x1,x0),max(x1,x0),tot);
        }else{
            int x=read();x=(x+ans-1)%39989+1;
            ans=t.ask(1,1,39990,x).second;
            printf("%d\n",ans);
        }
    }
    return 0;
}

当然李超线段树也可以维护区间最值：

P4069

代码：

#include<bits/stdc++.h>
using namespace std;
long long dis[1000100],atid[1000100],e,head[1000100],dep[1000100],siz[1000100],fa[1000100],son[1000100];
long long top[1000100],id[1000100],dfn,n,m,tot;
const long long inf=123456789123456789;
struct o{
    long long ne,to,w;
}a[1000100];
struct oo{
    long long xma,xmi,k,b;
    long long operator ()(long long x){
        return k*x+b;
    }
}g[1000100];
struct ooo{
    long long tree[1000100],mi[1000100];
    void init(){
        for(long long i=0;i<=1000000;i++){
            mi[i]=inf;
        }
    }
    long long ls(long long k){return k<<1;}
    long long rs(long long k){return k<<1|1;}
    void change(long long k,long long l,long long r,long long x,long long y,long long v){
        if(x<=l&&y>=r){
            mi[k]=min(mi[k],min(g[v](dis[atid[l]]),g[v](dis[atid[r]])));//维护答案 
            long long mid=(l+r)>>1; 
            if(g[v](dis[atid[mid]])<g[tree[k]](dis[atid[mid]])){
                swap(v,tree[k]);//维护大多数时候最优的  注意答案不能用mid更新
            }
            if(l==r) return;
            if(g[v](dis[atid[l]])<g[tree[k]](dis[atid[l]])) change(ls(k),l,mid,x,y,v);
            if(g[v](dis[atid[r]])<g[tree[k]](dis[atid[r]])) change(rs(k),mid+1,r,x,y,v);
            mi[k]=min(mi[k]/*不要忘了和自己比较*/,min(mi[ls(k)],mi[rs(k)]));//
            return;
        }
        long long mid=(l+r)>>1;
        if(x<=mid) change(ls(k),l,mid,x,y,v);
        if(y>mid) change(rs(k),mid+1,r,x,y,v);
        mi[k]=min(mi[k],min(mi[ls(k)],mi[rs(k)]));//
    }
    long long ask(long long k,long long l,long long r,long long x,long long y){
        if(x<=l&&y>=r){
            return mi[k];
        }
        long long mid=(l+r)>>1,res=min(g[tree[k]](dis[atid[max(l,x)]]),g[tree[k]](dis[atid[min(r,y)]]));//
        if(x<=mid) res=min(res,ask(ls(k),l,mid,x,y));
        if(y>mid) res=min(res,ask(rs(k),mid+1,r,x,y));
        return res;
    }
}t;
void dd(long long u,long long v,long long w){
    a[++e].ne=head[u];
    a[e].to=v;
    a[e].w=w;
    head[u]=e;
}
void dfs1(long long x,long long f){
    dep[x]=dep[f]+1;
    siz[x]=1;
    fa[x]=f;
    for(long long i=head[x];i;i=a[i].ne){
        long long v=a[i].to;
        if(v==f) continue;
        dis[v]=dis[x]+a[i].w;
        dfs1(v,x);
        siz[x]+=siz[v];
        if(!son[x]||siz[son[x]]<siz[v]) son[x]=v;
    }
}
void dfs2(long long x,long long tp){
    top[x]=tp;
    id[x]=++dfn;
    atid[dfn]=x;
    if(!son[x]) return;
    dfs2(son[x],tp);
    for(long long i=head[x];i;i=a[i].ne){
        long long v=a[i].to;
        if(v==fa[x]||v==son[x]) continue;
        dfs2(v,v);
    }
}
long long lca(long long x,long long y){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        x=fa[top[x]];
    }
    return dep[x]<dep[y]?x:y;
}
long long getdis(long long x,long long y){
    return dis[x]+dis[y]-(dis[lca(x,y)]<<1);
}
void change(long long x,long long y,long long v){
    while(top[x]!=top[y]){
        t.change(1,1,n,id[top[x]],id[x],v);
        x=fa[top[x]];
    }
    t.change(1,1,n,id[y],id[x],v);
}
long long ask(long long x,long long y){
    long long res=inf;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        res=min(res,t.ask(1,1,n,id[top[x]],id[x]));
        x=fa[top[x]];
    }
    if(dep[x]>dep[y]) swap(x,y);
    res=min(res,t.ask(1,1,n,id[x],id[y]));
    return res;
}
long long read(){
    char ch=getchar();long long x=0,f=1;
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch<='9'&&ch>='0'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
int main(){
    n=read();m=read();
    for(long long i=1;i<n;i++){
        long long u=read(),v=read(),w=read();
        dd(u,v,w);dd(v,u,w);
    }
    t.init();
    dfs1(1,0);dfs2(1,1);
    g[0].b=inf; //
    while(m--){
        long long op=read(),x=read(),y=read();
        if(op==1){
            long long k=read(),b=read();
            long long anc=lca(x,y);
            g[++tot].k=-k;
            g[tot].b=k*dis[x]+b;
            g[tot].xma=dis[x];
            g[tot].xmi=dis[anc];
            change(x,anc,tot);
            g[++tot].k=k;
            g[tot].b=b+k*dis[x]-2*k*dis[anc];
            g[tot].xma=dis[y];
            g[tot].xmi=dis[anc];
            change(y,anc,tot);
        }else{
            printf("%lld\n",ask(x,y));
        }
    }
    return 0;
}

可以和斜率优化结合：

P4655

转移显然有：f_i=min_{j=1}^{i-1}(f_j+(h_i-h_j)^2+sum_{i-1}-sum_j)

暴力O(n^2)，考虑优化。

先把平方展开：f_i=min_{j=1}^{i-1}(f_j+h_i^2+h_j^2-2h_ih_j+sum_{i-1}-sum_j)。

因为我们肯定是从f_j推到f_i，所以把j当成已知量处理，整理得到：f_i=min_{j=1}^{i-1}[(-2h_ih_j)+(f_j+h_j^2-sum_j)+(h_i^2+sum_{i-1})]

因为i是从2到n-1枚举的，所以h_i是变化的。显然对于每一个j(j<i),把h_i看成自变量，都有一个关于h_i的函数g_j(x)=(-2h_ix)+(f_j+h_j^2-sum_j)。这样就是李超线段树的模板题了。

代码：

#include<bits/stdc++.h>
using namespace std;
long long h[1000100],w[1000100],sum[1000100],tot;
struct oo{
    long long k,b;
    long long operator ()(long long x){
        return k*x+b;
    }
}a[1000100];
struct o{
    long long tree[8000100];
    long long ls(long long k){return k<<1;}
    long long rs(long long k){return k<<1|1;}
    void change(long long k,long long l,long long r,long long x,long long y,long long v){
        if(x<=l&&y>=r){
            long long mid=(l+r)>>1;
            if(a[v](mid)<a[tree[k]](mid)) swap(v,tree[k]);
            if(l==r) return;
            if(a[v](l)<a[tree[k]](l)) change(ls(k),l,mid,x,y,v);
            if(a[v](r)<a[tree[k]](r)) change(rs(k),mid+1,r,x,y,v);
            return;
        }
        long long mid=(l+r)>>1;
        if(x<=mid) change(ls(k),l,mid,x,y,v);
        if(y>mid) change(rs(k),mid+1,r,x,y,v);
    }
    long long ask(long long k,long long l,long long r,long long x){
        if(l==r){
            return a[tree[k]](l);
        }
        long long mid=(l+r)>>1;
        long long res=a[tree[k]](x);
        if(x<=mid) res=min(res,ask(ls(k),l,mid,x));
        else res=min(res,ask(rs(k),mid+1,r,x));
        return res;
    }
}t; 
long long read(){
    char ch=getchar();long long x=0,f=1;
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch<='9'&&ch>='0'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
long long pf(long long x){return x*x;}
int main(){
    int n=read();
    for(int i=1;i<=n;i++) h[i]=read();
    for(int i=1;i<=n;i++){
        long long x=read();sum[i]=sum[i-1]+x;
    }
    a[0].b=1e18+7;
    a[++tot].k=-2*h[1];
    a[tot].b=pf(h[1])-sum[1];
    t.change(1,0,1000000,0,1000000,tot);
    for(int i=2;i<n;i++){
        long long x=t.ask(1,0,1000000,h[i])+pf(h[i])+sum[i-1];
        a[++tot].k=-2*h[i];
        a[tot].b=pf(h[i])-sum[i]+x;
        t.change(1,0,1000000,0,1000000,tot);
    } 
    printf("%lld\n",t.ask(1,0,1000000,h[n])+pf(h[n])+sum[n-1]);
    return 0;
}

_4.可持久化线段树

@1基础

先看最简单的场景：对一个序列，每次更新只修改一个数，并把新序列当作一个新的版本。要查询某个版本序列的区间和。如果只保留最后版本的话很容易想到用线段树维护。但现在要维护多个版本，最简单的线段树已经不能达到目标了。思考一下，每次只改一个数，那么序列每次的变化其实是很小的，如果用线段树维护的话，不需要对整个序列重新建立一棵完整的线段树，只维护变化的节点就行了。根据这个思路，我们就可以创造出可持久化线段树了。

具体是这样操作的：每次修改，沿途新建，其余复制。在经典线段树上，每次修改都会有一个树上路径，由于新版本的线段树和旧版本的不一样，但又不能覆盖旧版本，所以沿途的每个节点都要新建。根据之前的思路，新节点的大部分信息与旧节点相同，所以可以先复制旧节点信息，只修改不同的部分。具体见代码：

int change(int pre,int l,int r,int x,int v){
    int k=++tot;
    tree[k]=tree[pre];
    if(l==r){
        tree[k].sum=v;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid) tree[k].ls=change(tree[pre].ls,l,mid,x,v);
    else tree[k].rs=change(tree[pre].rs,mid+1,r,x,v);
    tree[k].sum=tree[tree[k].ls].sum+tree[tree[k].rs].sum;
    return k;
}

不难发现一次修改最多修改logn个节点，时间复杂度、空间复杂度均为O(nlogn)。

那么区间修改、新建版本呢？其实也是可以的。由于懒标记的存在，我们可以积蓄修改操作，直到需要的时候再下传。主要操作依旧是沿途修改，其余复制，有些不同的是，在下传操作时也需要新建节点(因为下传之后信息发生变化，而旧节点可能仍在某个版本中需要被复用，所以需要新节点维护)，但如果是在修改操作时下传，在下传之后立马就要修改，那么刚刚新建的节点可能就直接被浪费了。但其实这不要紧，即使有浪费的情况，一次修改消耗的空间依然是O(logn)级别的，总空间复杂度为O(nlogn+mlogn)，浪费只会加常数，不影响算法的正确性。

模板题：

SP11470

代码：

#include<bits/stdc++.h>
using namespace std;
long long n,q,a[1000100],tot,rt[1000100];
struct o{
    long long ls,rs,sum,lan;
}tree[10000100];
long long clone(long long v){
    long long k=++tot;
    tree[k]=tree[v];
    return k;
}
void pup(long long k){
    tree[k].sum=tree[tree[k].ls].sum+tree[tree[k].rs].sum;
}
void build(long long &k,long long l,long long r){
    if(!k) k=++tot;
    if(l==r){
        tree[k].sum=a[l];
        return;
    }
    long long mid=(l+r)>>1;
    build(tree[k].ls,l,mid);
    build(tree[k].rs,mid+1,r);
    pup(k);
}
void add(long long k,long long l,long long r,long long v){
    tree[k].sum+=(r-l+1)*v;
    tree[k].lan+=v; 
}
void pud(long long k,long long l,long long r,long long mid){
    if(tree[k].lan){
        tree[k].ls=clone(tree[k].ls);
        tree[k].rs=clone(tree[k].rs);
        add(tree[k].ls,l,mid,tree[k].lan);
        add(tree[k].rs,mid+1,r,tree[k].lan);
        tree[k].lan=0;
    }
}
long long change(long long pre,long long l,long long r,long long x,long long y,long long v){
    long long k=clone(pre); 
    if(x<=l&&y>=r){
        add(k,l,r,v);
        return k;
    }
    long long mid=(l+r)>>1;
    pud(k,l,r,mid);
    if(x<=mid) tree[k].ls=change(tree[k].ls,l,mid,x,y,v);
    if(y>mid) tree[k].rs=change(tree[k].rs,mid+1,r,x,y,v);
    pup(k);
    return k;
}
long long ask(long long k,long long l,long long r,long long x,long long y){
    if(x<=l&&y>=r){
        return tree[k].sum;
    }
    long long mid=(l+r)>>1,res=0;
    pud(k,l,r,mid);
    if(x<=mid) res=ask(tree[k].ls,l,mid,x,y);
    if(y>mid) res+=ask(tree[k].rs,mid+1,r,x,y);
    return res;
}
long long read(){
    char ch=getchar();long long x=0,f=1;
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch<='9'&&ch>='0'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
int main(){
    n=read();q=read();
    for(long long i=1;i<=n;i++) a[i]=read();
    build(rt[0],1,n);
    long long t=0;
    while(q--){
        char op;cin>>op;
        long long x=read();
        if(op=='C'){
            long long y=read(),z=read();
            rt[t+1]=change(rt[t],1,n,x,y,z);
            ++t;
        }else if(op=='Q'){
            long long y=read();
            printf("%lld\n",ask(rt[t],1,n,x,y));
        }else if(op=='H'){
            long long y=read(),z=read();
            printf("%lld\n",ask(rt[z],1,n,x,y));
        }else{
            t=x;
        }
    }
    return 0;
}

@2经典应用

最基本的就是版本问题，即：修改但不抛弃，即我不仅会用到修改后的，修改前的我也会用到。

另一种就是可以把可持久化值域线段树当成前缀和处理。

即：除了版本问题，还有就是特殊的区间问题了，通常与“一个数在某个区间出现了多少次”有关(比如区间第k小是谁)。这时就可以建立可持久化值域线段树了。每插入一个值都当作是对原序列修改产生的一个新的版本，这样就可以用类似前缀和的方式去处理线段树上节点了。本质是：在r版本上i的出现次数-(l-1)版本上i的出现次数就是区间lr上i的出现次数。值域线段树上每个节点可以维护区间内所有数的出现次数之和，这样就很好处理了。

3.树状数组

略

4.分块

易错点

一定要考虑左右端点在同一个块内的情况，要特殊处理！！！

正文

分块就是将暴力做法放到一个块里面处理。询问时，两边的散块可以暴力处理，中间的整块可以非常快速地得到答案，从而将时间复杂度降到O(m \sqrt n)。

经验而言，块内对问题的答案是一定要维护的。

经典套路：

(1).带单点修改；找一段区间有多少数大于x

新创建一个数组b，用来存储一个块内的升序顺序。

询问：对散块直接暴力处理，整块用lower_bound在块内b数组快速查询，时间复杂度O(m\sqrt n logn)

修改：单点直接单个元素冒泡排序。如果是区间修改，尽量不要使用sort，很慢，可以观察一些性质来处理。

总复杂度O(m\sqrt n logn)。

(2).求区间众数(具体到是哪一个数)(不带修改)

维护p_{i,j}为块i,j的众数，sum_{i,j}为前i个块中j的出现次数。那么对一个询问，答案只可能为：散块里面出现过的数，中间整块的众数，数量是O(\sqrt n)级别的，直接暴力枚举可能的答案，时间复杂度O(m\sqrt n)。

5.莫队

根据排序对暴力进行优化的离线算法。

(1).经典莫队

按左端点所在块排序，相同则r升序排序。左端点移动复杂度O(\sqrt n)，右端点时间复杂度O(n)，总时间复杂度O(n\sqrt n)。

(2).带修莫队

带修改时，多出一个变量：修改的时间。变成x-y-z的三维问题。将块长调整为O(n^{\frac{2}{3}})，按依次按左端点所在块、右端点所在块、时间升序排序。左右端点移动很好处理，时间流动时要能同时做到实现修改和消除修改的影响(通常要用到swap)。总时间复杂度O(n^{\frac{5}{3}})。

(3).回滚莫队

当增加操作很好处理，但删除操作异常困难的时候，就可以上回滚莫队。

因为右端点单调递增，所以只有增加操作，要删除的只有左端点。那么可以考虑让左端点也只有增加操作，那就是从左端点所在块的右端点+1开始向左回滚，这样就只有增加操作了，且左端点回滚的时间复杂度仍为O(\sqrt n)。总时间复杂度O(n\sqrt n)。

(4).莫队二次离线

适用于：当区间(当前为l,r)扩展（或收缩）时（这里以r扩展到y为例），答案的变化量的形式为：l—r对r+1的贡献+\ \ l—r+1对r+2的贡献+\ \ ……\ +\ l—y-1对y的贡献，即\sum_{i=r+1}^{i \le y} f_i(l,i-1)，其中f_x(l,r)表示l—r对x的贡献。这种形式可以很容易地转化为前缀和的形式，即：设g_i=f_i(1,i-1)，pre_i=\sum_{j=1}^{j\le i} g_j，那么\sum_{i=r+1}^{i \le y} f_i(l,i-1)=pre_{y}-pre_{r}-\sum_{i=1}^{l-1}f_i(r+1,y) ，其中\sum_{i=1}^{l-1}f_i(r+1,y) 可以通过离线快速求出。右端点收缩、左端点（通常要用suf）扩展与收缩同理，且带有等式右边符号的改变。于是定义F(op,x,l,r)=op*\sum_{i=1}^{x}f_i(l,r)，其中op \in \{-1,1\}，那么F(op,l-1,r+1,y)=\sum_{i=1}^{l-1}f_i(r+1,y)，op的值根据分析而定，通常把所有F离线出来按x从小到大依次处理即可。因为F的l,r来源于询问的l,r变化，而通过莫队可把l,r的移动降低到O(n\sqrt n)，于是F的l,r的移动级别也是O(n\sqrt n)的。

含义：答案的计算需要多个量（这里简化为两个：A_{l,r},B_{l,r}），其中A_{l,r}可以用莫队快速求出，B_{l,r}的具体值和A_{l,r}有关，且不方便在莫队过程直接求出。但如果把所有B_{l,r}离线出来按线性依次处理很方便的话，就再把B_{l,r}也离线出来处理，因为是按线性依次处理的且来源于A_{l,r}，A_{l,r}的复杂度不超过O(n\sqrt n)，那么处理B_{l,r}的复杂度也不会超过O(n\sqrt n)，这样就可以在O(n\sqrt n)的复杂度内完成计算。

模板：https://www.luogu.com.cn/problem/P4887

做法（高度概括）：先求出bitcnt=k的数，令cnt_{a_i}表示a_i做第二个数，i前面有多少个数和它异或有k个1，用pre_i表示前i个数的cnt和，那么莫队r移动时要变化相应贡献，变化与pre和形如f(x,l,r,op)的式子有关，其中pre已求出，f(x,l,r,op)可以让x根据从小到大线性离线求出，l变化时同理，只不过要的是后缀和。

模板2：https://www.luogu.com.cn/problem/P5047

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,pos[100010],e,headsuf[100010],headpre[100010],block,a[100010];
int b[100010],t,bg[100010],ed[100010];
long long ans[100010],add[100010],addblock[100010],tree[100010],pre[100010],suf[100010];
struct o{
    int l,r,id;
    bool operator <(const o d) const{
        if(pos[l]!=pos[d.l]) return pos[l]<pos[d.l];
        if(pos[l]&1) return r<d.r;
        return r>d.r;
    }
}q[100010];
struct oo{
    int id,l,r,ne;
    long long op;
}qsuf[200010],qpre[200010];
int lowbit(int x){return x&(-x);}
void change(int x,int v){
    for(int i=x;i<=n;i+=lowbit(i)){
        tree[i]+=v;
    }
}
int ask(int x){
    int res=0;
    for(int i=x;i>0;i-=lowbit(i)){
        res+=tree[i];
    }
    return res;
}
void ddsuf(int id,int x,int l,int r,long long op){
    qsuf[++e].ne=headsuf[x];
    qsuf[e].id=id;
    qsuf[e].l=l;
    qsuf[e].r=r;
    qsuf[e].op=op;
    headsuf[x]=e;
}
void ddpre(int id,int x,int l,int r,long long op){
    qpre[++e].ne=headpre[x];
    qpre[e].id=id;
    qpre[e].l=l;
    qpre[e].r=r;
    qpre[e].op=op;
    headpre[x]=e;
}
int read(){
    char ch=getchar();int x=0,f=1;
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch<='9'&&ch>='0'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
int main(){
//  freopen("ce.in","r",stdin);
//  freopen("ce.out","w",stdout); 
    n=read();m=read();
    block=sqrt(n);
    for(int i=1;i<=n;i++) a[i]=read(),b[i]=a[i],pos[i]=(i-1)/block+1;
    for(int i=1;i<=m;i++){
        q[i].id=i;
        q[i].l=read();
        q[i].r=read();
    }
    t=n/block;
    if(n%block) t++;
    for(int i=1;i<=t;i++){
        bg[i]=(i-1)*block+1;
        ed[i]=i*block;
    }
    ed[t]=n;
    sort(q+1,q+1+m);
    int cnt=unique(b+1,b+1+n)-b-1;
    sort(b+1,b+1+cnt);
    for(int i=1;i<=n;i++){
        a[i]=lower_bound(b+1,b+1+cnt,a[i])-b;
    }
    for(int i=1;i<=n;i++){
        pre[i]=pre[i-1]+ask(n)-ask(a[i]);
        change(a[i],1);
    }
    for(int i=1;i<=n;i++) tree[i]=0;
    for(int i=n;i>0;i--){
        suf[i]=suf[i+1]+ask(a[i]-1);
        change(a[i],1);
    }
    int l=1,r=0;
    for(int i=1;i<=m;i++){
        if(q[i].l<l){
            ddsuf(q[i].id,r+1,q[i].l,l-1,-1);
            ans[q[i].id]+=suf[q[i].l]-suf[l];
        }
        if(q[i].l>l){
            ddsuf(q[i].id,r+1,l,q[i].l-1,1);
            ans[q[i].id]-=suf[l]-suf[q[i].l];
        }
        l=q[i].l;
        if(q[i].r>r){
            ddpre(q[i].id,l-1,r+1,q[i].r,-1);
            ans[q[i].id]+=pre[q[i].r]-pre[r];
        }
        if(q[i].r<r){
            ddpre(q[i].id,l-1,q[i].r+1,r,1);
            ans[q[i].id]-=pre[r]-pre[q[i].r];
        }
        r=q[i].r;
    }
    for(int x=0;x<=n;x++){
        if(x>0){
            for(int i=bg[pos[a[x]]];i<a[x];i++){
                add[i]++;
            }
            for(int i=1;i<pos[a[x]];i++){
                addblock[i]++;
            }
        }
        for(int i=headpre[x];i;i=qpre[i].ne){
            for(int j=qpre[i].l;j<=qpre[i].r;j++){
                ans[qpre[i].id]+=qpre[i].op*(add[a[j]]+addblock[pos[a[j]]]);
            }
        }
    }   
    for(int i=1;i<=t;i++) addblock[i]=0;
    for(int i=1;i<=n;i++) add[i]=0;
    for(int x=n+1;x>0;x--){
        if(x<=n){
            for(int i=a[x]+1;i<=ed[pos[a[x]]];i++){
                add[i]++;
            }
            for(int i=pos[a[x]]+1;i<=t;i++){
                addblock[i]++;
            }
        }
        for(int i=headsuf[x];i;i=qsuf[i].ne){
            for(int j=qsuf[i].l;j<=qsuf[i].r;j++){
                ans[qsuf[i].id]+=qsuf[i].op*(add[a[j]]+addblock[pos[a[j]]]);
            }
        }
    }
    for(int i=1;i<=m;i++){
        ans[q[i].id]+=ans[q[i-1].id];
    }
    for(int i=1;i<=m;i++){
        printf("%lld\n",ans[i]);
    }
    return 0;
}

声明（一定要看）

~虽然我的文章应该没人看但还是要~说明：这篇文章的初衷是自用的，主要写给自己看以总结提高、方便复习的，对内容的正确性不保证（当然大部分应该是对的），有错误可以指出

原始链接：a