查看: 1190|回復: 1

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

[複製鏈接]
  • TA的每日心情
    慵懶
    2015-4-10 14:18
  • 簽到天數: 78 天

    [LV.6]常住居民II

    176

    主題

    612

    帖子

    3959

    積分

    管理員

    Rank: 9Rank: 9Rank: 9

    積分
    3959

    台南一中資訊社新手達陣程式設計達人 - 2014

    發表於 2015-2-13 19:34:38 | 顯示全部樓層 |閱讀模式

    趕快加入我們來參與討論吧!

    您需要 登錄 才可以下載或查看,沒有帳號?加入我們

    x
    原題: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';
                    }
            }
    }
    




    回復

    使用道具 檢舉

  • TA的每日心情
    開心
    2015-4-12 10:09
  • 簽到天數: 137 天

    [LV.7]常住居民III

    142

    主題

    686

    帖子

    3559

    積分

    邁向天堂

    蘇多門

    Rank: 8Rank: 8

    積分
    3559

    新手達陣台南一中資訊社程式設計達人 - 2014

    發表於 2015-3-7 11:45:36 | 顯示全部樓層
    提供這題用墨隊算法的解法
    [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';
    	}
    }
    

    蘇多門 domen111
    My Web: https://sites.google.com/site/domenprg/
    回復 支持 反對

    使用道具 檢舉

    您需要登錄後才可以回帖 登入 | 加入我們

    本版積分規則

    快速回覆 返回頂部 返回列表