活动 做题记录

小清新数据结构题

题意

是个人能看懂

思路

考虑维护一颗权值线段树。在这颗线段树上，我们把满足度越高的排在越前面，即编号越小。

这可以通过对于原数组排序实现。

接着，我们对于每一次询问，在线段树上二分即可。

对于没一次修改，把它拆成两次操作。接着把它们按照时间排序即可。直接对对应点进行单点修改即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
static char buf[1000000],*p1=buf,*p2=buf;
#define getchar() p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++
inline int read(){int x=0,f=1;char c=getchar();while(c<'0' || c>'9'){if(c=='-') f=-1;c=getchar();}while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+c-48;c=getchar();}return x*f;}
inline void write(int x){static char buf[20];static int len=-1;if(x<0)putchar('-'),x=-x;do buf[++len]=x%10,x/=10;while(x);while(len>=0)putchar(buf[len--]+48);}

const int MAX = 4*500005;

struct node{
	int val, id;
	bool operator <	(const node & a) const{
		if(val != a.val)	return val > a.val;
		return id < a.id;
	} 
};

node a[MAX];

int s[MAX], sum[MAX];

void pushup(int x){
	s[x] = s[x<<1] ^ s[x<<1|1];
	sum[x] = sum[x<<1] + sum[x<<1|1];
}

void add(int l, int r, int pos, int pls, int x, int fuck){
	if(l == r){
		s[x] = pls * fuck;
		sum[x] = fuck;
		return ;
	}
	int mid = (l+r)>>1;
	if(pos <= mid)	add(l, mid, pos, pls, x<<1, fuck);
	else add(mid+1, r, pos, pls, x<<1|1, fuck);
	pushup(x);
}

int query(int l, int r, int pos, int x){
	if(l == r)	return s[x];	
	int mid = (l+r)>>1;	
	if(pos <= sum[x<<1])	return query(l, mid, pos, x<<1);
	else return s[x<<1] ^ query(mid+1, r, pos - sum[x<<1], x<<1|1);
}

struct event{
	int x, fl;
	int id;
	bool operator < (const event &a) const {
		if(a.x != x)	return x < a.x;
		return id < a.id;
	}
};
event p[4*MAX];
signed main(){
	int m = read(), n = read();
	for(int i = 1; i <= n; i++)	a[i].val = read(), a[i].id = i;
	sort(a+1, a+n+1);
	int cnt = 0;
	for(int i = 1; i <= n; i++){
		p[++cnt].x = read(), p[cnt].fl = 1;
		p[++cnt].x = read()+1, p[cnt].fl = 0;
	}
	for(int i = 1; i <= n; i++){
		p[a[i].id*2-1].id = i;
		p[a[i].id*2].id = i;
	}
	sort(p+1, p+cnt+1);
	int now = 1;
	for(int i = 1; i <= m; i++){
		while(p[now].x == i){
			add(1, n, p[now].id, a[p[now].id].id, 1, p[now].fl);
			now++;
		}
		int k = read();
		write(query(1, n, k, 1));
		puts("");
	}
	return 0;
}