The 2nd Universal Cup. Stage 1: Qingdao

G

Description

给定一个数列，每次ban一个位置，在每次ban之前，求连续子序列逆序对数的最大值，强制在线。（6s）\(n\leq10^5, \sum n \leq10^6\)

Solution

先考虑用权值线段树来维护区间逆序对数，不难支持在原数列前后加或删除一个数。然后考虑原题的分裂过程，将一段 \([l,r]\) 分裂成 \([l,p-1]\) 和 \([p+1,r]\) 两个区间，对于小的区间，直接暴力建一个新的线段树；对于大的区间，直接在 \([l,r]\) 的树上暴力减。

时间复杂度是 \(T(n) = 2T(\frac n2)+O(n\log n) = O(n\log ^2 n)\)

#include<bits/stdc++.h>
#define ll long long
#define irep(i,l,r) for(int i = l; i <= r; ++i)
#define drep(i,l,r) for(int i = r; i >= l; --i)
#define abs(x) (x > 0 ? x : -x)
using namespace std;

inline int read(){
	int s=0; bool fl = 0;
	char chcc=getchar();
	while(chcc<'0'||chcc>'9'){if(chcc == '-')fl = 1;chcc = getchar();}
	while(chcc>='0'&&chcc<='9') s=(s<<3)+(s<<1)+(chcc^48),chcc=getchar();
	return fl?-s:s;
}

struct segtree{
	int n, cur, siz;
	vector<array<int,5>>t;
	segtree(){}
	segtree(int maxn){
		n = maxn, cur = 0, siz = 0;
		t.push_back({0,maxn,-1,-1, 0});		
	}
	void init(int maxn){
		n = maxn, cur = 0, siz = 0;
		t.push_back({0,maxn,-1,-1, 0});		
	}
	void insert(int x,int v, int tim){
		if(x == -1)return;
		if(x == 0)siz += tim;
		auto [l,r,ls,rs,sum] = t[x];
		int mid = (l + r) >> 1;
		sum += tim;
		if(l == r){
			t[x] = {l,r,ls,rs,sum};
			return;
		}
		if(v <= mid){
			if(ls == -1){
				t.push_back({l, mid, -1, -1, 0});
				ls = ++ cur;
			}			
			t[x] = {l,r,ls,rs,sum};
			insert(ls, v, tim);
		}
		else{
			if(rs == -1){
				t.push_back({mid + 1, r ,-1, -1, 0});
				rs = ++ cur;
			}
			t[x] = {l,r,ls,rs,sum};
			insert(rs, v, tim);
		}
	}
	int query(int x, int v){
		if(x == -1)return 0;
		auto [l,r,ls,rs,sum] = t[x];	
		int mid = (l + r) >> 1;
		if(v < l)return 0;
		if(v >= r)return sum;
		return query(ls,v) + query(rs, v); 
	}
	segtree operator = (const int& mn){
		segtree tr(mn);
		return tr;	
	}
	void clear(){
		t.clear();
	}
	int size(){
		return siz;
	}
};
struct rg{
	int maxn;
	segtree t;
	ll sum = 0;
	void insert_back(int val){
		t.insert(0, val, 1);
		sum += t.size() - t.query(0, val);
	}
	void insert_front(int val){
		t.insert(0, val, 1);
		sum += t.query(0, val) - 1;
	}
	void del_front(int val){
		sum -= t.query(0, val) - 1;
		t.insert(0, val, -1);
	}
	void del_back(int val){
		sum -= t.size() - t.query(0, val);
		t.insert(0, val, -1);
	}
	int size(){
		return t.size();
	}
	rg(){}
	rg(int mx){
		sum = 0, maxn = mx;
		t.init(maxn);
	}
};
void solve(){
	int n = read();
	ll lstans = 0;
	set<int>st;
	multiset<ll>keys;
	vector<array<int,2>>arr;
	vector<int>a(n + 1);
	vector s(n + 1, rg(n));
	st.insert(-1);
	irep(i,0,n - 1)arr.push_back({read(),i});
	sort(arr.begin(), arr.end());
	irep(i,0,n - 1)a[arr[i][1]] = i;
	irep(i,0,n - 1)s[0].insert_back(a[i]);
	keys.insert(s[0].sum);
	irep(ii, 0, n - 1){
		lstans = *(-- keys.end());
		printf("%lld ",lstans);
		int pos = lstans ^ read();
		pos --;
		int l = *(-- st.lower_bound(pos)) + 1, r = l + s[l].size() - 1;
		keys.erase(keys.find(s[l].sum));
		if(s[l].size() < (pos - l) * 2){	
			for(int i = r; i > pos; --i){
				s[pos + 1].insert_front(a[i]);
				s[l].del_back(a[i]);
			}
			s[l].del_back(a[pos]);
		}else{
			for(int i = l; i < pos; ++i){
				s[l].del_front(a[i]);
				s[pos + 1].insert_back(a[i]);
			}
			s[l].del_front(a[pos]);
			swap(s[l], s[pos + 1]);
		}
		st.insert(pos);
		keys.insert(s[l].sum);
		if(pos + 1 < n)keys.insert(s[pos + 1].sum);
		
	}
	putchar('\n');
}

int main(){
	int T = read();
	while(T --)solve();
	return 0;
}