bzoj3809

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3809

题目大意：

　　　　Autumn和Bakser又在研究Gty的妹子序列了！但他们遇到了一个难题。

　　　　对于一段妹子们，他们想让你帮忙求出这之内美丽度∈[a,b]的妹子的美丽度的种类数。

　　　　为了方便，我们规定妹子们的美丽度全都在[1,n]中。

　　　　给定一个长度为n(1<=n<=100000)的正整数序列s(1<=si<=n)，对于m(1<=m<=1000000)次询问“l,r,a,b”，每次输出sl...sr中，权值∈[a,b]的权值的种类数。

题解：莫队+树状数组

代码：

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<algorithm>

 #define maxn 100000

 using namespace std;

 int n,m;

 int pos[maxn],val[maxn],c[maxn],bo[maxn],ans[maxn*];

 struct data{

     int l,r,a,b,id;

 }a[maxn*];

 int read()

 {

     int x=; char ch; bool bo=;

     while (ch=getchar(),ch<''||ch>'') if (ch=='-') bo=;

     while (x=x*+ch-'',ch=getchar(),ch>=''&&ch<='') ;

     if (bo) return -x; return x;

 }

 int lowbit(int x){ return x&-x;

 }

 void add(int x,int v)

 {

     for (int i=x; i<=n; i+=lowbit(i)) c[i]+=v;

 }

 int query(int x)

 {

     int res=;

     for (int i=x; i; i-=lowbit(i)) res+=c[i];

     return res;

 }

 bool cmp(data a,data b)

 {

     if (pos[a.l]==pos[b.l])

         if (pos[a.l]&) return a.r<b.r;

         else return a.r>b.r;

     return pos[a.l]<pos[b.l];

 }

 void init()

 {

     n=read(),m=read();

     for (int i=; i<=n; i++) val[i]=read();

     for (int i=; i<=m; i++)

     {

         a[i].l=read(),a[i].r=read(),a[i].a=read(),a[i].b=read(); a[i].id=i;

     }

     int kk=int (sqrt(n));

     for (int i=; i<=n; i++) pos[i]=(i-)/kk+;

     sort(a+,a++m,cmp);

 }

 void updata(int k,int vval)

 {

     if (vval==-)

     {

         if (bo[val[k]]==)    add(val[k],-);

         bo[val[k]]--;

     }

     else

     {

         if (!bo[val[k]]) add(val[k],);

         bo[val[k]]++;

     }

 }

 void work()

 {

     int r=,l=;

     for (int i=; i<=m; i++)

     {

         for (; r<a[i].r; r++) updata(r+,);

         for (; r>a[i].r; r--) updata(r,-);

         for (; l<a[i].l; l++) updata(l,-);

         for (; l>a[i].l; l--) updata(l-,);

         ans[a[i].id]=query(a[i].b)-query(a[i].a-);

     }

     for (int i=;i<=m; i++)

         printf("%d\n",ans[i]);

 }

 int main()

 {

     init();

     work();

 }

注：还是我太渣，都垫底了，据说还可以分块+莫队，会快的飞起。