hdu 3874 Necklace（線段樹）

這道題目和我之前做過的一道3xian大牛出的題目很像，不過總的來說還是要簡單一點兒。   計算區間內的值的時候如果兩個值相等，只能計算其中一個。   這道題需要將所有的問題輸入之後再計算，首先，對所有問題的右邊界進行排序。從左到有依次插入數組中的數據，並記錄數據的位置，如果該數據之前記錄過，在重新記錄時需要將之前記錄的數據修改為0。一邊插入數據，一邊還要比較i和記錄的問題的右邊界，如果i大於等於當前問題的右邊界，計算當前問題的值，並記錄在ans數組裡面，記錄之後開始檢查下一個問題。到最後，所有數據都記錄之後，重新一起輸出。   1A！

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define N 200005
struct node
{
	int x,y;
	__int64 sum;
}a[N];
struct Q
{
	int x,y;
	int id;
}q[N];
int b[N];
int mark[N*5];
void CreatTree(int t,int x,int y)
{
	a[t].x=x;
	a[t].y=y;
	a[t].sum=0;
	if(x==y)
		return ;
	int mid=(x+y)/2;
	int temp=t*2;
	CreatTree(temp,x,mid);
	CreatTree(temp+1,mid+1,y);
	return ;
}
void InsertTree(int t,int x,int k)
{
	if(a[t].x==a[t].y)
	{
		a[t].sum+=k;
		return ;
	}
	int temp=t*2;
	int mid=(a[t].x+a[t].y)/2;
	if(x<=mid)
		InsertTree(temp,x,k);
	else
		InsertTree(temp+1,x,k);
	a[t].sum=a[temp].sum+a[temp+1].sum;
	return ;
}
__int64 FindTree(int t,int x,int y)
{
	__int64 ans;
	ans=0;
	if(a[t].x==x&&a[t].y==y)
		return a[t].sum;
	int temp=t*2;
	int mid=(a[t].x+a[t].y)/2;
	if(y<=mid)
		ans=FindTree(temp,x,y);
	else if(x>mid)
		ans=FindTree(temp+1,x,y);
	else
	{
		ans+=FindTree(temp,x,mid);
		ans+=FindTree(temp+1,mid+1,y);
	}
	return ans;
}
int cmp(const void *a,const void *b)
{
	return (*(Q *)a).y-(*(Q *)b).y;
}
	__int64 ans[N];
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		int n;
		scanf("%d",&n);
		CreatTree(1,1,n);
		int i;
		for(i=1;i<=n;i++)
			scanf("%d",&b[i]);
		int m;
		scanf("%d",&m);
		for(i=1;i<=m;i++)
		{
			scanf("%d%d",&q[i].x,&q[i].y);
			q[i].id=i;
		}
		qsort(q+1,m,sizeof(q[0]),cmp);
		int k;
		k=1;
		memset(mark,0,sizeof(mark));
		for(i=1;i<=n;i++)
		{
			int flag;
			flag=mark[b[i]];
			if(flag)
				InsertTree(1,flag,-b[i]);
			InsertTree(1,i,b[i]);
			mark[b[i]]=i;
			while(q[k].y<=i&&k<=m)
			{
				ans[q[k].id]=FindTree(1,q[k].x,q[k].y);
				k++;
			}
		}
		for(i=1;i<=m;i++)
			printf("%I64d\n",ans[i]);
	}
	return 0;
}