此题莫队可过

然而太难了......

我在胡雨菲那看的解法，然后自己打了一波，调了一个错，上交，自信AC。

做法：离线，对于L排序。

每种颜色可能出现很多次，那么我们如何不算重复呢？

只需把[L,n]区间内第一个出现的该颜色标为1即可。

所以我们记录下每个下标i所对应的颜色下一次出现的位置next[i]即可。

每次L挪动时，挪动的每个位置都-1(一定是1不是0)，然后把next[i]+1即可。

所求即为∑[1,R]。

 

1 #include 
      
        2 #include 
       
         3 #define lowbit(a) (a&(-a)) 4 #define say(a) printf(#a); 5 #define ln printf("\n"); 6 using namespace std; 7 const int N = 500010; 8  9 struct Question10 {11     int L,R,ans,num;12 }quest[200010];13 int next[N],lastfind[N],x[N],tree[N],a[N];14 int n;15 bool cmp1(Question x,Question y) {
    return x.L
        
         0;i-=lowbit(i)) ans+=tree[i];28     return ans;29 }30 int main()31 {32     scanf("%d",&n);33     for(int i=1;i<=n;i++) scanf("%d",&a[i]),x[i]=a[i];34     int m;35     scanf("%d",&m);36     for(int i=1;i<=m;i++) scanf("%d%d",&quest[i].L,&quest[i].R),quest[i].num=i;37     sort(x+1,x+n+1);38     int k=0;39     for(int i=1;i<=n;i++) if(x[i]!=x[i-1]) x[++k]=x[i]; /// 离散化40     for(int i=1;i<=n;i++)41     {42         int p=lower_bound(x+1,x+k+1,a[i])-x;///预处理出next[i]43         if(lastfind[p]) next[lastfind[p]]=i;44         else add(i,1);///p -> i 这里调一个错，之前写的p45         lastfind[p]=i;46     }47     int j=1,ans=0;48     //for(int i=1;i<=6;i++) printf("%d ",getsum(i)-getsum(i-1));ln;49     sort(quest+1,quest+m+1,cmp1);50     for(int i=1;i<=m;i++)51     {52         while(j
        
       
      

 

用了一些特殊的调试手法。。。