采花 flower

题目描述

 

萧芸斓是 Z 国的公主，平时的一大爱好是采花。

今天天气晴朗，阳光明媚，公主清晨便去了皇宫中新建的花园采花。花园足够大，容纳 了 n 朵花，花有 c 种颜色（用整数 1-c 表示），且花是排成一排的，以便于公主采花。

公主每次采花后会统计采到的花的颜色数，颜色数越多她会越高兴！同时，她有一癖好， 她不允许最后自己采到的花中，某一颜色的花只有一朵。为此，公主每采一朵花，要么此前 已采到此颜色的花，要么有相当正确的直觉告诉她，她必能再次采到此颜色的花。

由于时间关系，公主只能走过花园连续的一段进行采花，便让女仆福涵洁安排行程。福 涵洁综合各种因素拟定了 m 个行程，然后一一向你询问公主能采到多少朵花（她知道你是编 程高手，定能快速给出答案！），最后会选择令公主最高兴的行程（为了拿到更多奖金！）。 

 

 

输入

 

第一行四个空格隔开的整数 n、c 以及 m。

接下来一行 n 个空格隔开的整数，每个数在[1, c]间，第 i 个数表示第 i 朵花的颜色。

接下来 m 行每行两个空格隔开的整数 l 和 r（l ≤ r），表示女仆安排的行程为公主经 过第 l 到第 r 朵花进行采花。

 

 

输出

 

共m行，每行一个整数，第i个数表示公主在女仆的第i个行程中能采到的花的颜色数。

 

 

样例输入

5 3 51 2 2 3 11 51 22 22 33 5

样例输出

20010

提示

 

【样例说明】  

询问[1, 5]：公主采颜色为 1 和 2 的花，由于颜色 3 的花只有一朵，公主不采；

询问[1, 2]：颜色 1 和颜色 2 的花均只有一朵，公主不采；

询问[2, 2]：颜色 2 的花只有一朵，公主不采；

询问[2, 3]：由于颜色 2 的花有两朵，公主采颜色 2 的花；

询问[3, 5]：颜色 1、2、3 的花各一朵，公主不采。

【数据范围】  

对于 20%的数据，n ≤ 102，c ≤ 102，m ≤ 102；

对于 50%的数据，n ≤ 105，c ≤ 102，m ≤ 105；

对于 100%的数据，1 ≤ n ≤106，c ≤ n，m ≤ 106。 

 

 

来源

---

解法好牛

首先离线处理询问

按l从小到大排序

维护区间(l,n)

 把[l, n]内每种颜色的第一朵花标记成1，其余标记为0，那么[l, r]内标记的和就是区间内花的种类数； 

每种颜色的第一朵花标记成1、第二朵花标记成-1，其余标记为0，那么[l, r]内标记的和就是区间内相同颜色只有一朵的花的种类数；

上面两数之差就是答案

树状数组维护即可

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define maxn 1000006using namespace std;int n,c,m,s[maxn],a[maxn],b[maxn],num[maxn],t,top[maxn],ans[maxn];vector
           
            g[maxn];struct no{ int id,l,r;}q[maxn];bool cmp(no a, no b){ return a.l
            
             >n>>c>>m; for(int i=1;i<=n;i++){ scanf("%d",&s[i]); g[s[i]].push_back(i); num[s[i]]++; if(num[s[i]]==1){ pa(i,1),pb(i,1); } if(num[s[i]]==2)pb(i,-1); } for(int i=1;i<=m;i++){ scanf("%d%d",&q[i].l,&q[i].r); q[i].id=i; } sort(q+1,q+m+1,cmp); int la=1; for(int i=1;i<=m;i++){ while(la