[IOICAMP2015][線段樹]62 - 草莓園保衛戰 III

Sylveon

原題：http://judge.ioicamp.org/problems/62
AC：http://judge.ioicamp.org/submissions/6871

可持久化線段樹XD，懶得分配記憶體，用了超過原儲存區域的30倍空間ZZZ。
第 I 個線段樹的點J為：到第[tex]i[/tex]項前，[tex]A_j[/tex]是不是最後一次出現的，是的話就是1，不是就是0。
範測第一筆做出來的大概就像這樣：

[Plain Text] 純文本查看 復制代碼

2
6 2
3 1 4 1 5 9

(第一個0是多做出來的，別理他)

[Plain Text] 純文本查看 復制代碼

線段樹1:0 1 0 0 0 0 0
線段樹2:0 1 1 0 0 0 0
線段樹3:0 1 1 1 0 0 0
線段樹4:0 1 0 1 1 0 0
線段樹5:0 1 0 1 1 1 0
線段樹6:0 1 0 1 1 1 1

查詢[tex](i,j)[/tex]的話就是把第[tex]j[/tex]顆線段樹的[tex](i,j)[/tex]加起來就好了

[C++] 純文本查看 復制代碼

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<map>
#include<set>
using namespace std;
struct node{
        int sum;
        int l,r;
};
node data[5000000] = {0,0,0};
inline int sum(int i){ return i?data[i].sum:0; }
//MEMCT
int _id;
void init(){
        _id=0;
}
int copy(int c)
{
        int newid = ++_id;
        data[newid] = data[c] ;
        return newid;
}
//RMQ
int modify(int res,int i,int v,int L,int R)
{
        int n = copy(res);
        if( L == R )
        {
                data[n].sum += v;
                return n;
        }
        int M = (L+R)/2;
        if( i <= M )data[n].l = modify( data[n].l ,i, v , L , M );
        else                data[n].r = modify( data[n].r ,i, v ,M+1, R );
        data[n].sum = sum(data[n].l) + sum(data[n].r) ;
        return n;
}
int query(int r1,int l,int r,int L,int R)
{
        if(L==l&&R==r)
                return sum(r1);
        int M = (L+R)/2;
        if( r <= M ) return query( data[r1].l , l , r , L , M );
        if( M <  l ) return query( data[r1].r , l , r , M+1,R );
        return         query( data[r1].l , l , M , L , M ) + 
                        query( data[r1].r , M+1,r , M+1,R ) ;
}
int head[ 100001 ];
int last[ 100001 ];
int buf [ 100001 ];
int main()
{
        ios::sync_with_stdio(false);
        cin.tie(0);
        int T,tmp,N,M,a,b;
        cin>>T;
        set<int> st;
        map<int,int> mp;
        while(T--)
        {
                cin>>N>>M;
                st.clear();
                mp.clear();
                init();
                for(int i=1;i<=N;++i)
                {
                        cin>>buf[i];
                        st.insert(buf[i]);
                }
                tmp=0;
                for(int c:st)
                        mp[c]=tmp++;
                for(int i=1;i<=N;++i)
                        buf[i]=mp[buf[i]];
                int L = 0;
                int R = N;
                //BUILD
                memset(last,0,sizeof(last));
                for(int i=1;i<=N;++i)
                {
                        int z = last[ buf[i] ];
                        if( z != 0 )
                                head[i] = modify(head[i-1],z,-1,L,R);
                        else
                                head[i] = head[i-1];
                        last[ buf[i] ] = i;
                        head[i] = modify(head[i],i,1,L,R);
                }
                while(M--)
                {
                        cin>>a>>b;
                        if(a>b)swap(a,b);
                        cout<<query(head[b],a,b,L,R)<<'\n';
                }
        }
}

domen111

提供這題用墨隊算法的解法

[C++] 純文本查看 復制代碼

#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<vector>
#include<unordered_map>
using namespace std;
int a[100010];
int b[100010];
struct ques{
	int l,r;
	int qid,bid;
}qs[100010];
int ans[100010];
bool cmp(ques a,ques b)
{
	if(a.bid!=b.bid) return a.bid<b.bid;
	else return a.r<b.r;
}
int mp[100010],cou;
inline void add(int n)
{
	if(mp[n]==0)
		cou++;
	mp[n]++;
//	cout<<"add "<<n<<endl;
}
inline void sub(int n)
{
	mp[n]--;
	if(mp[n]==0)
		cou--;
//	cout<<"sub "<<n<<endl;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int T;
	cin>>T;
	while(T--)
	{
		int n,m;
		cin>>n>>m;
		for(int i=0;i<n;i++)
			cin>>a[i];
		
		//discretization
		//discretization way-1-lower_bound (1291 ms)
		for(int i=0;i<n;i++)
			b[i]=a[i];
		sort(b,b+n);
		for(int i=0;i<n;i++)
			a[i]=lower_bound(b,b+n,a[i])-b;
		//discretization way-2-pair (1242 ms)
//		vector<pair<int,int>> tmp(n);
//		for(int i=0;i<n;i++)
//			tmp[i]=make_pair(a[i],i);
//		sort(tmp.begin(),tmp.end());
//		int lst=0,k=0;
//		for(int i=0;i<n;i++)
//		{
//			if(tmp[i].first!=lst)k++;
//			a[tmp[i].second]=k;
//			lst=tmp[i].first;
//		}
		
		//solve
		int K=sqrt(n);
		for(int i=0;i<m;i++)
		{
			int l,r;
			cin>>l>>r;
			qs[i]={l-1,r-1,i,(l-1)/K};
		}
		sort(qs,qs+m,cmp);
		memset(mp,0,sizeof mp);
		cou=0;
		int l=0,r=-1;
		for(int i=0;i<m;i++)
		{
			while(qs[i].r>r)
			{
				r++;
				add(a[r]);
			}
			while(qs[i].l<l)
			{
				l--;
				add(a[l]);
			}
			while(qs[i].r<r)
			{
				sub(a[r]);
				r--;
			}
			while(qs[i].l>l)
			{
				sub(a[l]);
				l++;
			}
			ans[qs[i].qid]=cou;
		}
		for(int i=0;i<m;i++)
			cout<<ans[i]<<'\n';
	}
}