2018 ICPC 青岛网络赛 Couleur

题意：

给出一个长度为n的序列，每次将某个子序列分成两段，输出所有段中逆序对最大的数目。

题解：

假设从x位置断开，找到x最左边的断点l，和最右边的断点r，那么就是把区间(l,r)分解为(l,x)和(x,r)，如何维护两段的逆序对个数呢？

启发式分解

假设断点更靠近r，我们暴力求解出(x,r)的逆序对个数，再求解出(l,x)和(x,r)中两段各有一个数的逆序对的个数，也就是有交叉的逆序对个数，再让(l,r)中的逆序对个数减去那两项就是(l,x)的逆序对个数。

暴力求解的方法：

将区间(x,r)中的元素建立名次树，每加入一个元素之前看树中大于它的个数，累加就是(x,r)的逆序对个数。

(l,x)是一颗名次树，枚举(x,r)中的元素，看在(l,x)中大于它的个数，累加有交叉的逆序对个数。

进而求得(l,x)的逆序对个数。

假设断点更靠近l，方法基本和上面的一样，不过需要一个交换树的操作，原因请自己思考。

用的函数是pb_ds中rb_tree中的order_of_key

注意由于rb_tree中不能有重复元素，需要用结构体，然后重载大于号

#include<bits/stdc++.h>
#include<hash_map>
#define N 100010
#define INF 0x3f3f3f3f
#define eps 1e-10
#define pi 3.141592653589793
#define LL long long
#define pb push_back
#define cl clear
#define si size
#define lb lower_bound
#define ook order_of_key
#define mem(x) memset(x,0,sizeof x)
#define sc(x) scanf("%d",&x)
#define scc(x,y) scanf("%d%d",&x,&y)
#define sccc(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
struct node{
    int v,id;
    node(int a,int b){v=a;id=b;}
    bool operator >(node b) const
    {return v==b.v?id>b.id:v>b.v;}
};
tree<node,null_type,greater<node>,rb_tree_tag,tree_order_statistics_node_update> T[N];
int a[N];
set<int>st; map<int,LL>mp; multiset<LL>A;
int f[N];
int main()
{
    int TT;
    sc(TT);
    while(TT--)
    {
        int n; sc(n);
        for (int i=1;i<=n;i++) sc(a[i]),f[i]=i;f[0]=0;
        LL ans=0; st.clear(); mp.clear(); A.clear();
        st.insert(0); st.insert(n+1);
        for (int i=1;i<=n;i++)
        {
            ans+=T[0].order_of_key(node(a[i],i));
            T[0].insert(node(a[i],i));
        }
        mp[0]=ans; A.insert(ans);
        for (int i=1;i<=n;i++)
        {
            auto p=A.end(); p--; ans=*p;
            printf("%lld",ans); if (i<n) printf(" ");else puts("");
            int x,l,r; sc(x); x^=ans;
            auto pos=st.upper_bound(x); r=*pos;
            pos--; l=*pos; LL tot=mp[l],tt=0,tmp=0;
            A.erase(A.lb(tot)); st.insert(x);
            if (r-x<x-l)
            {
                int tl=f[l],tx=f[x];
                for (int i=x+1;i<r;i++)
                {
                    T[tl].erase(node(a[i],i));
                    tmp+=T[tx].ook(node(a[i],i));
                    T[tx].insert(node(a[i],i));
                }
                mp[x]=tmp; A.insert(tmp);
                for (int i=x+1;i<r;i++)
                    tmp+=T[tl].ook(node(a[i],i));
                tot=tot-tmp-T[tl].ook(node(a[x],x));
                mp[l]=tot; A.insert(tot);
                T[tl].erase(node(a[x],x));
            }else
            {
                swap(f[l],f[x]);
                int tl=f[l],tx=f[x];
                for (int i=l+1;i<x;i++)
                {
                    T[tx].erase(node(a[i],i));
                    tmp+=T[tl].ook(node(a[i],i));
                    T[tl].insert(node(a[i],i));
                }
                mp[l]=tmp; A.insert(tmp);
                for (int i=l+1;i<x;i++)
                    tmp+=r-x-T[tx].ook(node(a[i],i));
                T[tx].erase(node(a[x],x));
                tot=tot-tmp-r+x+1+T[tx].ook(node(a[x],x));
                mp[x]=tot; A.insert(tot);
            }
        }
    }
    return 0;
}

UPDATA

不用结构体，用long long会更快一点

#include<bits/stdc++.h>
#include<hash_map>
#define N 100010
#define INF 0x3f3f3f3f
#define eps 1e-10
#define pi 3.141592653589793
#define LL long long
#define pb push_back
#define cl clear
#define si size
#define lb lower_bound
#define ook order_of_key
#define mem(x) memset(x,0,sizeof x)
#define sc(x) scanf("%d",&x)
#define scc(x,y) scanf("%d%d",&x,&y)
#define sccc(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
tree<LL,null_type,greater<LL>,rb_tree_tag,tree_order_statistics_node_update> T[N];
LL a[N];
set<int>st; unordered_map<int,LL>mp; multiset<LL>A;
int f[N];

int main()
{
    int TT;
    sc(TT);
    while(TT--)
    {
        int n,x; sc(n);
        for (int i=1;i<=n;i++) { sc(x); a[i]=x; a[i]=a[i]<<20|i; f[i]=i;} f[0]=0;
        LL ans=0; st.clear(); mp.clear(); A.clear();
        st.insert(0); st.insert(n+1);
        for (int i=1;i<=n;i++)
        {
            ans+=T[0].order_of_key((a[i]));
            T[0].insert((a[i]));
        }
        mp[0]=ans; A.insert(ans);
        for (int i=1;i<=n;i++)
        {
            auto p=A.end(); p--; ans=*p;
            printf("%lld",ans); if (i<n) printf(" ");else puts("");
            int x,l,r; sc(x); x^=ans;
            auto pos=st.upper_bound(x); r=*pos;
            pos--; l=*pos; LL tot=mp[l],tt=0,tmp=0;
            A.erase(A.lb(tot)); st.insert(x);
            if (r-x<x-l)
            {
                int tl=f[l],tx=f[x];
                for (int i=x+1;i<r;i++)
                {
                    T[tl].erase((a[i]));
                    tmp+=T[tx].ook((a[i]));
                    T[tx].insert((a[i]));
                }
                mp[x]=tmp; A.insert(tmp);
                for (int i=x+1;i<r;i++)
                    tmp+=T[tl].ook((a[i]));
                tot=tot-tmp-T[tl].ook((a[x]));
                mp[l]=tot; A.insert(tot);
                T[tl].erase((a[x]));
            }else
            {
                swap(f[l],f[x]);
                int tl=f[l],tx=f[x];
                for (int i=l+1;i<x;i++)
                {
                    T[tx].erase((a[i]));
                    tmp+=T[tl].ook((a[i]));
                    T[tl].insert((a[i]));
                }
                mp[l]=tmp; A.insert(tmp);
                for (int i=l+1;i<x;i++)
                    tmp+=r-x-T[tx].ook((a[i]));
                T[tx].erase((a[x]));
                tot=tot-tmp-r+x+1+T[tx].ook((a[x]));
                mp[x]=tot; A.insert(tot);
            }
        }
    }
    return 0;
}