我不知道题解应该叫什么名字

· · 题解

都说这题简单，然后我做了一个下午并调了一个晚上。我谔谔，吾常见笑于大方之家。

记一个数 x 首次出现于 first_x，最后一次出现于 last_x。

一个很经典的结论：区间本质不同逆序对就是在寻找这样的点对：x>y，且 first_x < last_y，此处取首次出现和最后一次出现的正确性显然。

发现这长的非常像 cdq 分治。

考虑维护一个 set，这样可以在 O(m \log n) 的时间复杂度预处理出每一次修改对 first 和 last 的改变。

考虑一种比较简单的实现，每一次更改都先把之前的信息都删除掉，然后再加回来，这样写 cdq 的时候就不需要加一大堆特判。

考虑定义每一次修改为 (id,val,tim,op,tp)，代表在第 tim 时刻，将 op 中下标为 id 的位置修改为了 val，贡献参数为 tp。

声明一下 op 和 tp 的定义。

随后使用 cdq 实现寻找点对即可。

注意一下别把 val 和 pos 搞混了，我把这个写反了调了一个晚上。

:::success[代码]

#include<bits/stdc++.h>
#define lowbit(x) (x&(-x))
#define mid ((l+r)>>1)
#define ll long long
using namespace std;

const int N=1e5+5,M=1e6+5;
struct node{int tim,op,tp,val,pos;}a[M];int cnt;
int A[N],first[N],last[N],n;set<int> s[N];ll ans[N];
struct item{//树状数组 BIT
    int c[N];
    inline void add(int x,int k){x++;for(int i=x;i<=n+1;i+=lowbit(i)) c[i]+=k;}
    inline int ask(int x){x++;int ans=0;for(int i=x;i;i-=lowbit(i)) ans+=c[i];return ans;}
}BIT;
/*
tim 代表修改时间
op=0/1 分别代表修改 first/last
tp=-1/1 记录当前的贡献为正还是负
更改了 val 的信息，将其改为了 pos
*/

inline int read(){
    int s=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
    return s*f;
}

inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}

inline void clear(int tim,int x){//在 tim 时刻清除 x 的贡献
    if(first[x] && last[x]){
        a[++cnt]={tim,0,-1,x,first[x]};
        a[++cnt]={tim,1,-1,x,last[x]};
        first[x]=last[x]=0;//清空 first 和 last
    }
}

inline void push(int tim,int x){//在 tim 时刻记录 x 的贡献
    if(s[x].empty()) return;
    first[x]=*s[x].begin();
    last[x]=*s[x].rbegin();
    a[++cnt]={tim,0,1,x,first[x]};
    a[++cnt]={tim,1,1,x,last[x]};
}

inline bool cmp1(node x,node y){
    if(x.pos!=y.pos) return x.pos>y.pos;
    return x.op>y.op;
}

inline bool cmp2(node x,node y){return x.tim<y.tim;}

inline void cdq(int l,int r){
    if(l>=r) return;
    cdq(l,mid);cdq(mid+1,r);
    /*
    我们要找的是 (first,now) 的点对
    根据分治思想，我们当前就要合并两侧互相的贡献
    所以，需要处理 “ 左 last & 右 first ” 和 “ 左 first & 右 last ” 
    */
    //1.左 last & 右 first
    int j=l;
    for(int i=mid+1;i<=r;i++){
        for(;j<=mid && a[j].tim<=a[i].tim;j++)//转移的时候要注意维护时间的偏序
            if(a[j].op) BIT.add(a[j].val,a[j].tp);//左侧 last，我们在对应位置放入信息
        if(!a[i].op) ans[a[i].tim]+=BIT.ask(a[i].val-1)*a[i].tp;//右侧 first，查询信息
    }
    for(int i=l;i<j;i++) 
        if(a[i].op) BIT.add(a[i].val,-a[i].tp);//注意一下这里不能够直接设为 0，只能够手动清除产生的贡献
    //2.左 first & 右 last
    j=mid+1;
    for(int i=l;i<=mid;i++){
        for(;j<=r && a[j].tim<a[i].tim;j++)//转移的时候要注意维护时间的偏序
            if(!a[j].op) BIT.add(a[j].val,a[j].tp);//右侧 last，我们在对应位置放入信息
        if(a[i].op) ans[a[i].tim]+=(BIT.ask(n)-BIT.ask(a[i].val))*a[i].tp;
    }
    for(int i=mid+1;i<j;i++)
        if(!a[i].op) BIT.add(a[i].val,-a[i].tp);;//注意一下这里不能够直接设为 0，只能够手动清除产生的贡献
    inplace_merge(a+l,a+mid+1,a+r+1,cmp2);
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++) A[i]=read(),s[A[i]].insert(i);//放入对应位置
    for(int i=1;i<=n;i++) push(0,i);//记录初始贡献
    int q;cin>>q;
    for(int i=1;i<=q;i++){
        int x=read(),k=read();
        if(A[x]==k) continue;//已经是当前值了
        clear(i,A[x]);s[A[x]].erase(x);push(i,A[x]);//原本值的贡献
        A[x]=k;clear(i,k);s[k].insert(x);push(i,k);//新的值的贡献
    }
    sort(a+1,a+cnt+1,cmp1);cdq(1,cnt);
    for(int i=1;i<=q;i++) ans[i]+=ans[i-1];//前缀和得到答案
    for(int i=0;i<=q;i++) cout<<ans[i]<<"\n";
    return 0;
}

:::