HDU 6703 array 權值線段樹

http://www.caiyiwen.tech/article/5.html

• 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;
}