D，http://acm.uestc.edu.cn/#/problem/show/1584


题意：平面上n个点，询问每个点左下方的点有多少个？

解法：排序（以Y坐标为第一关键字，X坐标为第二关键字）+树状数组


#include <bits/stdc++.h>
using namespace std;
const int maxn=100010;
int n,rnk[maxn],c[maxn];
struct node{
    int x,y;
}a[maxn];
bool cmp(node x, node y){
    if(x.y==y.y) return x.x<y.x;
    return x.y<y.y;
}
inline int lowbit(int x){
    return x&-x;
}
void add(int x){
    while(x<maxn){
        c[x]++;
        x+=lowbit(x);
    }
}
int sum(int x){
    int ans=0;
    while(x>0){
        ans+=c[x];
        x-=lowbit(x);
    }
    return ans;
}
int main()
{
    int n;
    while(~scanf("%d",&n)){
        for(int i=1; i<=n; i++) scanf("%d %d", &a[i].x,&a[i].y);
        sort(a+1,a+n+1,cmp);
        memset(rnk,0,sizeof(rnk));
        memset(c,0,sizeof(c));
        for(int i=1; i<=n; i++){
            rnk[sum(a[i].x)]++;
            add(a[i].x);
        }
        for(int i=1; i<n; i++) printf("%d\n", rnk[i-1]);
        printf("%d\n", rnk[n-1]);
    }
    return 0;
}

E，http://acm.uestc.edu.cn/#/problem/show/1583

题意：一个排列，用最少的交换次数次数变换到另一个排列，每次只能交换相邻两个元素。

解法：处理一个数组d，d[i]表示a[i]应该到b数组哪个位置。答案就是d数组的逆序对数

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
typedef long long LL;
int n,a[maxn],c[maxn];
void add(int x){
    while(x<maxn){
        c[x]++;
        x+=x&-x;
    }
}
int sum(int x){
    int ans=0;
    while(x>0){
        ans+=c[x];
        x-=x&-x;
    }
    return ans;
}

int main()
{
    while(~scanf("%d",&n)){
        memset(c,0,sizeof(c));
        memset(a,0,sizeof(a));
        LL ans=0;
        for(int i=1; i<=n; i++){
            int x; scanf("%d", &x); a[x]=i;
        }
        for(int i=1; i<=n; i++){
            int x; scanf("%d", &x);
            ans+=1LL*(sum(n)-sum(a[x]-1));
            add(a[x]);
        }
        printf("%lld\n", ans);
    }
    return 0;
}

F,http://acm.uestc.edu.cn/#/problem/show/1582

题意：给你n个元素的数组{a}，m次询问，每次给你一个数X，每次问你max{a1 xor X, a2 xor X, …, an xor X}

解法：对{a}里每个元素的二进制串从高位到低位建立trie（零一字典树）
询问时贪心（显然，让更高位的二进制位为1是要更优的）地向下，如果x该位是1，那么走0，如果是0，那么走1。
如果该位仅有1或0，那没办法，只能往这里走。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e7+2;
struct node{
    int root,tot,ch[maxn][2];
    int newnode(){
        ch[tot][0]=ch[tot][1]=-1;
        return tot++;
    }
    void init(){
        tot=0,root=newnode();
    }
    void Insert(int x){
        int now=root;
        for(int j=30; j>=0; j--){
            int go=(x&(1<<j))?1:0;
            if(ch[now][go]==-1){
                ch[now][go]=newnode();
                now=ch[now][go];
            }
            else{
                now=ch[now][go];
            }
        }
    }
    int query(int x){
        int now=root;
        int ans=0;
        for(int j=30; j>=0; j--){
            int go=(x&(1<<j))?1:0;
            if(ch[now][!go]!=-1) ans|=(1<<j),now=ch[now][!go];
            else now=ch[now][go];
        }
        return ans;
    }
}trie;
int main()
{
    int n, q;
    while(~scanf("%d",&n)){
        trie.init();
        for(int i=1; i<=n; i++){
            int x;
            scanf("%d",&x);
            trie.Insert(x);
        }
        scanf("%d",&q);
        while(q--){
            int x;
            scanf("%d", &x);
            printf("%d\n", trie.query(x));
        }
    }
    return 0;
}