C++14(g++5.4) 解法, 执行用时: 202ms, 内存消耗: 5264K, 提交时间: 2020-02-22 13:29:57

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> point;
#define fi first
#define se second
const int N = 1e5 + 10;
int r[N], s[N];
int ch[N][2], fa[N], sz[N], dep[N];
int bit[N], n, q;
void add(int x, int v){for(;x<=n;x+=x&-x)bit[x]+=v;}
void add(int l, int r, int v){add(l,v),add(r+1,-v);}
int query(int x){int ret=0;for(;x>0;x-=x&-x)ret+=bit[x];return ret;}
void init() {
    for(int i = 1; i <= n; i++) {
        bit[i] = fa[i] = dep[i] = 0;
        ch[i][0] = ch[i][1] = 0;
        sz[i] = 1;
    }
}
void up(int x) {
    sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + 1;
}
void setfa(int x, int y, bool _r) {
    if(y) ch[y][_r] = x;
    if(x) fa[x] = y;
}
void build() {
    vector<int> stk;
    int nowroot = 0;
    for(int i = 1; i <= n; i++) {
        while(!stk.empty() && s[stk.back()] < s[i]) stk.pop_back();
        if(!stk.empty()) {
            setfa(ch[stk.back()][1], i, 0);
            setfa(i, stk.back(), 1);
        } else {
            setfa(nowroot, i, 0);
            nowroot = i;
        }
        stk.push_back(i);
    }
    for(int i = 1; i <= n; i++) up(r[i]);
    for(int i = n; i > 0; i--) dep[r[i]] = dep[fa[r[i]]] + 1;
    for(int i = 1; i <= n; i++) add(i, dep[i] - dep[i - 1]);
}
int rot(int &x, int &y) {
    int ret = 0;
    if(fa[x] != y) {
        ret = 2 * abs(query(x) - query(y));
    } else {
        int k = ch[y][1] == x;
        ret = sz[ch[x][k]] + sz[ch[y][k^1]];
        add(y - k*sz[ch[y][k^1]], y + (k^1)*sz[ch[y][k^1]], 1);
        add(x - (k^1)*sz[ch[x][k]], x + k*sz[ch[x][k]], -1);
        setfa(ch[x][k^1], y, k);
        setfa(x, fa[y], ch[fa[y]][1] == y);
        setfa(y, x, k^1);
        up(y);
        up(x);
    }
    swap(x, y);
    return ret;
}

int main() {
#ifdef local
    freopen("in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int _; cin >> _;
    while(_--) {
        cin >> n >> q;
        for(int i = 1; i <= n; i++) cin >> r[i], s[r[i]] = i;
        init();
        build();
        while(q--) {
            int x; cin >> x;
            cout << rot(r[x], r[x + 1]) << '\n';
        }
    }
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 273ms, 内存消耗: 8796K, 提交时间: 2020-04-28 16:44:39

#include<bits/stdc++.h>
using namespace std;

int read(){int a; scanf("%d" , &a); return a;}
const int _ = 1e5 + 7;
int fa[_] , ch[_][2] , ql[_] , qr[_] , val[_] , pos[_] , dep[_] , N , Q , T , stk[_] , top;

#define lowbit(x) x & -x
int arr[_]; void add(int x , int v){while(x <= N){arr[x] += v; x += lowbit(x);}}
int qry(int x){int sum = 0; while(x){sum += arr[x]; x -= lowbit(x);} return sum;}

void upd(int x){ql[x] = ch[x][0] ? ql[ch[x][0]] : x; qr[x] = ch[x][1] ? qr[ch[x][1]] : x;}
void dfs(int x){if(x){dep[ch[x][0]] = dep[ch[x][1]] = dep[x] + 1; dfs(ch[x][0]); dfs(ch[x][1]); upd(x);}}
int rot(int x){
	add(ql[x] , -1); add(qr[x] + 1 , 1);
	bool f = ch[fa[x]][1] == x; int ans = qr[ch[x][f]] - ql[ch[x][f]] + 1 , y = fa[x] , z = fa[y] , w = ch[x][f ^ 1];
	fa[x] = z; ch[z][ch[z][1] == y] = x; fa[y] = x; ch[x][f ^ 1] = y; fa[w] = y; ch[y][f] = w;
	upd(y); upd(x); add(ql[y] , 1); add(qr[y] + 1 , -1); return ans + qr[ch[y][f ^ 1]] - ql[ch[y][f ^ 1]] + 1;
}

int main(){
	qr[0] = -1; val[0] = 1e9;
	for(T = read() ; T ; --T){
		N = read(); Q = read(); for(int i = 1 ; i <= N ; ++i){pos[i] = read(); val[pos[i]] = i;}
		top = 0; memset(ch , 0 , sizeof(ch)); memset(arr , 0 , sizeof(arr));
		for(int i = 1 ; i <= N ; ++i){
			int pre = 0; while(val[stk[top]] < val[i]) pre = stk[top--];
			fa[ch[stk[top]][1] = i] = stk[top]; fa[ch[i][0] = pre] = i; stk[++top] = i;
		}
		dfs(stk[1]); for(int i = 1 ; i <= N ; ++i) add(i , dep[i] - dep[i - 1]);
		while(Q--){
			int p = read() , &x = pos[p] , &y = pos[p + 1];
			printf("%d\n" , fa[x] == y ? rot(x) : 2 * abs(qry(x) - qry(y)));
			swap(x , y);
		}
	}
	return 0;
}