题目链接

• B - array
  • 训练时花了很久才想明白如何建模，这是因为对于权值线段树还没有足够的感觉所致。经过寒假在家中的个人训练，已经初步掌握其常见技巧。我们可以明显地看到，操作1的“+1e7”远大于n的上界，所以远大于数组中元素的上界。所以只要进行过一次操作1，这个元素已经形同虚设，失去了在操作2中的约束性。
  • 做法一 - 权值线段树：对这个array建立一个维护元素下标和区间最大值的权值线段树。每逢操作1，可以将此元素对应的下标改为INF；每逢操作2，二分找到权值线段树上第一个的≥k且下标大于r的值，即为答案。
  • 做法二：主席树：对这个array建立一棵主席树，每逢操作1，删除原值，赋予新值（可指定所有被修改过后的数为一个INF以节省空间）；每逢操作2，找到[r+1,n]区间上的最小值即可。

代码：

#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=(int)1e5+10;
int ori[MAXN],a[MAXN],ans[MAXN<<2];
inline void PushUp(int rt)
{
    ans[rt]=max(ans[rt<<1],ans[rt<<1|1]);
}
void Build(int l,int r,int rt)
{
    if(l==r)
    {
        ans[rt]=a[l];
        return;
    }
    int mid=(l+r)>>1;
    Build(l,mid,rt<<1);
    Build(mid+1,r,rt<<1|1);
    PushUp(rt);
}
void Change(int L,int C,int l,int r,int rt)
{
    if(l==r)
    {
        ans[rt]=C;
        return;
    }
    int mid=(l+r)>>1;
    if(L<=mid)
    {
    	Change(L,C,l,mid,rt<<1);
	}
    else
    {
    	Change(L,C,mid+1,r,rt<<1|1);
	}
    PushUp(rt);
}
int Query(int K,int R,int l,int r,int rt)
{
	if(l==r)
	{
		return l;
	}
	int mid=(l+r)>>1;
	int ANS=0x3f3f3f3f;
	if(K<=mid&&R<ans[rt<<1])
	{
		ANS=Query(K,R,l,mid,rt<<1);
		if(ANS!=0x3f3f3f3f)
		{
			return ANS;
		}
	}
	if(R<ans[rt<<1|1])
	{
		return Query(K,R,mid+1,r,rt<<1|1);
	}
	return ANS;
}
bool cmp(int a,int b)
{
	return ori[a]<ori[b];
}
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		int n,m;
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;++i)
		{
			scanf("%d",&ori[i]);
			a[i]=i;
		}
		a[n+1]=0x3f3f3f3f;
		sort(a+1,a+1+n,cmp);
		Build(1,n+1,1);
		int LastAns=0;
		while(m--)
		{
			int op;
			scanf("%d",&op);
			if(op==1)
			{
				int t1;
				scanf("%d",&t1);
				Change(ori[t1^LastAns],0x3f3f3f3f,1,n+1,1);
			}
			else
			{
				int t2,t3;
				scanf("%d%d",&t2,&t3);
				int r=t2^LastAns;
				int k=t3^LastAns;
				LastAns=Query(k,r,1,n+1,1);
				printf("%d\n",LastAns);
			}
		}
	}
	return 0;
}