普通莫队

技术文章 1年前 (2020) 完美者
1,876 0

标签:com   put   space   输入   main   r++   blocks   its   出现   

```

/*例题:

Description:

有n个数字,数字k,m个查询。

每次查询的格式是L,r,求L~r(左右包含)这个区间内数字的出现次数刚好是k的数字种数。

范围:n<=30000,k<=n,m<=30000,1<=L<r<=n,数列中元素大小<=n。

输入n,k,m,然后n个元素,然后m行查询,对于每一个询问,输出正确的答案。

Example input:

5 2 3

1 2 3 2 2

1 2

2 4

1 5

Example output:

0

1

0
以下代码是洛谷P1972 [SDOI2009]HH的项链的莫队做法 即例题k为1的情况
*/
#include <bits/stdc++.h>
using namespace std;
void in(int &x){
x=0;char c=getchar();
int y=1;
while(c<‘0‘||c>‘9‘){if(c==‘-‘)y=-1;c=getchar();}
while(c>=‘0‘&&c<=‘9‘){x=(x<<3)+(x<<1)+c-‘0‘;c=getchar();}
x*=y;
}
void o(int x){
if(x<0){x=-x;putchar(‘-‘);}
if(x>9)o(x/10);
putchar(x%10+‘0‘);
}
int blocks;
struct question{
int l;
int r;
int id;
}qst[1000010];//离线查询
bool comp(const question & a,const question & b)//查询的比较函数
{
return (a.l/blocks<b.l/blocks)||(a.l/blocks==b.l/blocks&&a.r<b.r);
}
int sum,cnt[1000010],l=0,r=0,ans[1000010];
int a[1000010];
void pls(int A)//增加一个数
{
cnt[A]++;
if(cnt[A]==1)
{
sum++;
}
}
void mns(int B)//减小一个数
{
cnt[B]--;
if(cnt[B]==0)
{
sum--;
}
}
int main()
{
int m,n,k;
in(n);
blocks=(n-1)/(int)sqrt(n)+1;//分块的大小,向上取整?
for(int i=1;i<=n;i++)in(a[i]);
in(m);
for(int i=1;i<=m;i++){
in(qst[i].l);in(qst[i].r);
qst[i].id=i;
}
sort(qst+1,qst+m+1,comp); //以l为第一关键字,以r为第二关键字 排序
for(int i=1;i<=m;i++)
{
while(r<qst[i].r)
r++,pls(a[r]);

while(r>qst[i].r)
mns(a[r]),r--;

while(l<qst[i].l)
mns(a[l]),l++;

while(l>qst[i].l)
l--,pls(a[l]);
ans[qst[i].id]=sum;
}
for(int i=1;i<=m;i++){
o(ans[i]);putchar(‘\n‘);
}
return 0;
}

```

普通莫队

标签:com   put   space   输入   main   r++   blocks   its   出现   

原文地址:https://www.cnblogs.com/yesuweiYYYY/p/13912487.html

版权声明:完美者 发表于 2020-11-02 10:50:50。
转载请注明:普通莫队 | 完美导航

暂无评论

暂无评论...