1 条题解
-
0
luogu7764[COCI2016-2017#5] Poklon
莫队解法
看了题面之后,便知道能用莫队做。 我们知道数组中的数据范围是小于 的自然数,而 。我们知道了要离散化 离散化代码:
for(int i=1;i<=n;i++){ cin>>a[i]; b[i]=a[i]; } sort(b+1,b+1+n); m1=unique(b+1,b+1+n)-b;//去重用的STL for(int i=1;i<=n;i++){ a[i]=lower_bound(b+1,b+1+m1,a[i])-b; }
然后我们可以很快得打出莫队模板,然后就是修改的问题。 当这个数出现后,我们要统计它出现的次数,这个用桶维护。如果它出现的次数为 ,说明答案加 。如果出现的次数为 ,则说明统计前它出现的次数为 ,答案要减 。 代码:
void add(int k){ cnt[k]++; if(cnt[k]==2)sum++; else if(cnt[k]==3)--sum; }
反之,同理可得。在删除数据时,如果它出现的次数为 ,说明答案加 。如果出现的次数为 ,则说明统计前它出现的次数为 ,答案要减 。 代码:
void del(int k){ --cnt[k]; if(cnt[k]==2)P(sum); else if(cnt[k]==1)--sum; }
完整代码
#include<cstdlib> #include<cstring> #include<cstdio> #include<cctype> #include<cmath> #include<algorithm> typedef long long LL; typedef unsigned long long ULL; namespace FastIo{ typedef __uint128_t ULLL; static char buf[100000],*p1=buf,*p2=buf,fw[100000],*pw=fw; #define gc p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++ inline void pc(const char &ch){ if(pw-fw==100000)fwrite(fw,1,100000,stdout),pw=fw; *pw++=ch; } #define fsh fwrite(fw,1,pw-fw,stdout),pw=fw struct FastMod{ FastMod(ULL b):b(b),m(ULL((ULLL(1)<<64)/b)){} ULL reduce(ULL a){ ULL q=(ULL)((ULLL(m)*a)>>64); ULL r=a-q*b; return r>=b?r-b:r; } ULL b,m; }HPOP(10); struct QIO{ char ch; int st[40]; template<class T>inline void read(T &x){ x=0,ch=gc; while(!isdigit(ch))ch=gc; while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=gc;} } template<class T>inline void write(T a){ do{st[++st[0]]=HPOP.reduce(a);a/=10;}while(a); while(st[0])pc(st[st[0]--]^48); pc('\n'); } }qrw; } using namespace FastIo; #define NUMBER1 500000 #define P(A) A=-~A #define fione_i(begin,end) for(register int i=begin;i<=end;P(i)) int n,m,fk,cnt[NUMBER1+5],a[NUMBER1+5],b[NUMBER1+5],ans[NUMBER1+5],sum(0); struct ASK{ int l,r,id; bool operator<(const ASK &A)const{return l/fk==A.l/fk?r<A.r:l<A.l;} }ask[NUMBER1+5]; inline void add(int k){ P(cnt[k]); if(cnt[k]==2)P(sum); else if(cnt[k]==3)--sum; } inline void del(int k){ --cnt[k]; if(cnt[k]==2)P(sum); else if(cnt[k]==1)--sum; } signed main(){ int l(1),r(0),m1; qrw.read(n); qrw.read(m); fk=sqrt(n); fione_i(1,n){ qrw.read(a[i]); b[i]=a[i]; } std::sort(b+1,b+1+n); m1=std::unique(b+1,b+1+n)-b; fione_i(1,n)a[i]=std::lower_bound(b+1,b+1+m1,a[i])-b; fione_i(1,m){ qrw.read(ask[i].l); qrw.read(ask[i].r); ask[i].id=i; } std::sort(ask+1,ask+1+m); fione_i(1,m){ while(l<ask[i].l)del(a[l++]); while(l>ask[i].l)add(a[--l]); while(r>ask[i].r)del(a[r--]); while(r<ask[i].r)add(a[++r]); ans[ask[i].id]=sum; } fione_i(1,m)qrw.write(ans[i]); fsh; exit(0); return 0; }
- 1
信息
- ID
- 6652
- 时间
- 5000ms
- 内存
- 500MiB
- 难度
- 5
- 标签
- 递交数
- 4
- 已通过
- 2
- 上传者