rt

评测姬WA 10pts

评测结果

本地测第一个测试点AC

代码

#include <iostream>
#include <cstdio>
#define rep(i, l, r) for(int i = l; i <= r; ++ i)
#define repd(i, r, l) for(int i = r; i >= l; -- i)

using namespace std;

const int N = 200010;
const int MAX = 200000;
typedef long long ll;

int n, m;
struct Segment_Tree
{
	int lc, rc;
	ll sum;
	#define lson t[i].lc
	#define rson t[i].rc
	#define sum(i) t[i].sum
} t[N * 20];
int root[N], tot;
int rubbish[N * 20], cnt = 0;
int cnttree = 1;

int build()
{
	if(cnt) return rubbish[cnt--];
	t[++tot].sum = t[tot].lc = t[tot].rc = 0;
	return tot;
}
void Delete(int &i)
{
	lson = rson = sum(i) = 0;
	rubbish[++cnt] = i;
	i = 0;
}
void up(int i)
{
	sum(i) = sum(lson) + sum(rson);
}
void insert(int i, int l, int r, int val, int delta)
{
	if(l == r)
	{
		sum(i) += delta;
		return;
	}
	int mid = (l + r) >> 1;
	if(val <= mid)
	{
		if(!lson) lson = build();
		insert(lson, l, mid, val, delta);
	}
	else
	{
		if(!rson) rson = build();
		insert(rson, mid + 1, r, val, delta);
	}
	up(i);
}
ll query(int i, int l, int r, int ql, int qr)
{
	if(ql <= l && qr >= r) return sum(i);
	ll ans = 0;
	int mid = (l + r) >> 1;
	if(ql <= mid) ans += query(lson, l, mid, ql, qr);
	if(qr > mid) ans += query(rson, mid + 1, r, ql, qr);
	return ans;
}
void split(int &p, int &q, int l, int r, int ql, int qr)
{
	if(qr < l || ql > r) return;
	if(!p) return;
	if(ql <= l && qr >= r)
	{
		q = p;
		p = 0;
		return;
	}
	if(!q) q = build();
	int mid = (l + r) >> 1;
	split(t[p].lc, t[q].lc, l, mid, ql, qr);
	split(t[p].rc, t[q].rc, mid + 1, r, ql, qr);
	up(p);
	up(q);
}
void merge(int &p, int &q, int l, int r)
{
	if(!p || !q)
	{
		p += q;
		return;
	}
	if(l == r)
	{
		sum(p) += sum(q);
		Delete(q);
		return;
	}
	int mid = (l + r) >> 1;
	merge(t[p].lc, t[q].lc, l, mid);
	merge(t[p].rc, t[q].rc, mid + 1, r);
	up(p);
	Delete(q);
}
int query_kth(int i, int l, int r, ll k)
{
	if(!i) return -1;
	if(l == r) return l;
	int mid = (l + r) >> 1;
	if(k <= sum(lson)) return query_kth(lson, l, mid, k);
	else return query_kth(rson, mid + 1, r, k - sum(lson));
	return -1;
}
int main()
{
//	freopen("P5494_1.in", "r", stdin);
//	freopen("data.out", "w", stdout);
	scanf("%d%d", &n, &m);
	tot = 0; root[1] = build();
	rep(i, 1, n)
	{
		int x;
		scanf("%d", &x);
		insert(root[1], 1, MAX, i, x);
	}
	rep(i, 1, m)
	{
		int op, p, q, x, y, t;
		ll k;
		scanf("%d", &op);
		if(op == 0)
		{
			scanf("%d%d%d", &p, &x, &y);
			split(root[p], root[++cnttree], 1, MAX, x, y);
		}
		if(op == 1)
		{
			scanf("%d%d", &p, &t);
			merge(root[p], root[t], 1, MAX);
		}
		if(op == 2)
		{
			scanf("%d%d%d", &p, &x, &q);
			insert(root[p], 1, MAX, q, x);
		}
		if(op == 3)
		{
			scanf("%d%d%d", &p, &x, &y);
			printf("%lld\n", query(root[p], 1, MAX, x, y));
		}
		if(op == 4)
		{
			scanf("%d%lld", &p, &k);
			if(query(root[p], 1, MAX, 1, MAX) < k) puts("-1");
			else printf("%d\n", query_kth(root[p], 1, MAX, k));
		}
	}
	return 0;
}