Codeforece E. Anton and Permutation

主席树算贡献l,r中交换位置，算出>=rank(h) 和 <=rank(h)  a[l],a[r] 先不统计 a[l]比a[r]大的话交换后ans-1，a[l]比a[r]小的话交换后ans-1，ans+<r的，->r的 ans-<l的，+>l的，区间比k大的数量或者区间第k大等类似的可以用第二类主席树弄

#include <cstdio>

#include <memory>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <vector>

#include <cassert>

#include <string>

#include <ctime>

#include <map>

#include <queue>

#include <algorithm>

#include <iostream>

#include <cassert>

#include <set>

using namespace std;

#define REP(i,n) for(int i=0;i<n;i++)

#define rep(i,a,b) for(int i=a;i<=b;i++)

#define req(i,a,b) for(int i=a;i>=b;i--)

#define rp(i,a) for(int i=head[a];i+1;i=edge[i].next)

#define cl(a,b) memset(a,b,sizeof a);

#define ll long long

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define mod 10007

const int inf = ~0u >> 2;

const ll INF = (1LL << 62) - 1;

double eps = 1e-12;

const int N = 500005 + 5;

const int M = 200005;

int n, m, d;

int a[500005];

int rnk[N];

int root[N];

int croot[N];

int sz = 0, tot = 0;

void insert(int &num, int val, int k, int l, int r);

struct Node {

	int sum;

	int ch[2];

}T[30500010];

void insert(int &num, int val, int k, int l, int r, int flag) {

	if (flag == 0 || num == 0) {

		T[++sz] = T[num]; num = sz;

	}

	T[num].sum += val;

	if (l == r) {

		return;

	}

	int m = (l + r) >> 1;

	if (k <= m) {

		insert(T[num].ch[0], val, k, l, m, flag);

	}

	else {

		insert(T[num].ch[1], val, k, m + 1, r, flag);

	}

}

int query(int i, int j, int k, int l, int r) {

	if (k > T[j].sum - T[i].sum)

		k = T[i].sum - T[i].sum;

	if (l == r)

		return l;

	int m = (l + r) >> 1;

	if (k <= T[T[j].ch[0]].sum - T[T[i].ch[0]].sum)

		return query(T[i].ch[0], T[j].ch[0], k, l, m);

	else

		return query(T[i].ch[1], T[j].ch[1], k - (T[T[j].ch[0]].sum - T[T[i].ch[0]].sum), m + 1, r);

}

void add(int x, int num, int d) {

	while (x <= tot) {

		insert(croot[x], d, num, 1, tot, 1);

		x += x&-x;

	}

}

struct Pack {

	vector<int> v;

	Pack() {}

	Pack(int x) { v.push_back(x); }

	void operator +=(int x) {

		v.push_back(x);

	}

	operator ll()const {//得到左孩子和

		ll ret = 0;

		for (int i = 0; i<v.size(); i++)

			ret += T[T[v[i]].ch[0]].sum;

		return ret;

	}

	void lt() {

		for (int i = 0; i < v.size(); i++)

			v[i] = T[v[i]].ch[0];

	}

	void rt() {

		for (int i = 0; i < v.size(); i++)

			v[i] = T[v[i]].ch[1];

	}

};

Pack sum(int x, int k) {

	Pack ret;

	while (x>0) {

		ret += croot[x];

		x -= x&-x;

	}

	return ret;

}

ll binSearch(int l, int r, int k) {

	Pack treesl = sum(l,0);

	Pack treesr = sum(r,0);

	Pack presl = Pack(root[l]);

	Pack presr = Pack(root[r]);

	int xl = 1, xr = tot;

	ll ret = 0;

	int rtl = root[l];

	int rtr = root[r];

	while (xl < xr) {

		int mid = (xl + xr) >> 1;

		ll t = treesr - treesl + presr - presl;

		if (mid <= k) {

			ret += t;

			treesr.rt(); treesl.rt(); presr.rt(); presl.rt();

			//ret += T[T[rtr].ch[0]].sum - T[T[rtl].ch[0]].sum;

			xl = mid+1;

			if (mid == k) {

				ret--;

				break;

			}

		}

		else {

			treesr.lt(); treesl.lt(); presr.lt(); presl.lt();

			xr = mid;

		}

	}

	return ret;

}

struct Seg {

	int l, r, h, x;

}q[M];

int val[N];

int cnt = 0;

int Hash(int x) {

	return lower_bound(val, val + tot, x) - val + 1;

}

int b[N];

int main() {

	//for (int i = 0; i <= sz; i++)T[i] = T[0];

	cnt = 0;

	sz = 0;

	tot = 0;

	scanf("%d%d", &n, &m);

	for (int i = 1; i <= n; i++) {

		a[i] = i;

		b[i] = i;

		val[cnt++] = a[i];

	}

	for (int i = 0; i < m; i++) {

		int x, y;

		scanf("%d%d", &x, &y);

		if (x > y)

			swap(x, y);

		q[i * 4].l = x;

		q[i * 4].r = y;

		q[i * 4].h = b[y];

		q[i * 4].x = -1;

		q[i * 4 + 1].l = x;

		q[i * 4 + 1].r = y;

		q[i * 4 + 1].h = b[x];

		q[i * 4 + 1].x = -2;

		q[i*4+2].x = x;

		q[i*4+2].h = b[y];

		//val[cnt++] = b[y];

		q[i*4+2].l = -inf;

		q[i * 4+3].x = y;

		q[i * 4+3].h = b[x];

		//val[cnt++] = b[x];

		q[i * 4+3].l = -inf;

		swap(b[x], b[y]);

			/*if (l<1 || r>n || l>r || h<1 || h>r - l + 1)

				assert(false);*/

	}

	sort(val, val + cnt);

	rnk[0] = ++tot;

	for (int i = 1; i < cnt; i++) {

		if (val[i] != val[i - 1])

			rnk[i] = ++tot;

		else

			rnk[i] = tot;

	}

	for (int i = 0; i <= tot; i++)croot[i] = 0;

	unique(val, val + cnt);

	root[0] = 0;

	for (int i = 1; i <= n; i++) {

		root[i] = root[i - 1];

		insert(root[i], 1, Hash(a[i]), 1, tot, 0);

	}

	ll ans = 0;

	for (int i = 0; i < 4*m; i++) {

		if (q[i].l != -inf) {

			if (q[i].x == -1) {

				if (q[i].l != q[i].r) {

					ll tmp = binSearch(q[i].l - 1, q[i].r, Hash(q[i].h));

					if (a[q[i].l] < a[q[i].r])

						tmp--;

					ans += tmp;

					ans -= max(0LL, (q[i].r - q[i].l - tmp - 1));

				}

				//printf("%d\n", val[binSearch(q[i].l - 1, q[i].r, q[i].h) - 1]);

			}

			if (q[i].x == -2) {

				if (q[i].l != q[i].r) {

					ll tmp = binSearch(q[i].l - 1, q[i].r, Hash(q[i].h));

					if (a[q[i].l] > a[q[i].r])

						tmp--;

					ans -= tmp;

					ans += max(0LL, (q[i].r - q[i].l - tmp - 1));

				}

				if (a[q[i].l] > a[q[i].r])

					ans--;

				else if(a[q[i].l]<a[q[i].r])

					ans++;

				cout << ans << endl;

			}

		}

		else {

			add(q[i].x, Hash(a[q[i].x]), -1);

			a[q[i].x] = q[i].h;

			add(q[i].x, Hash(q[i].h), 1);

		}

	}

	//cout << ans << endl;

	/*for (int i = 1; i <= tot; i++)

		croot[i] = 0, val[i] = 0, a[i] = 0;*/

	return 0;

}

巴特西

Codeforece E. Anton and Permutation

最新文章

热门文章