page

我会带着你远行 2023-06-01 15:54 56阅读 0赞

#### page ####

![mg0M4I.png][]

这道题目在\\(luogu\\)上有原题--[P3419 \[POI2005\]SAM-Toy Cars][P3419 _POI2005_SAM-Toy Cars]。

这道题在\\(ZR\\)时候老师讲过，但是当时讲的是堆做法，比较麻烦，也没有写出来，所以考试的时候写的是权值线段树的做法。

#include<iostream> #include<cstdio> #include<queue> using namespace std; const int N=2e5+100; struct Tree{ int ls,rs,sum; }t[N<<1]; deque<int>q[N]; int n,k,ans,cnt=1; int a[N],tp[N]; bool mark[N]; inline void push_up(int rt) { t[rt].sum=t[t[rt].ls].sum+t[t[rt].rs].sum; return ; } inline int query(int rt,int l,int r,int k) { if (l==r) return l; int sz=t[t[rt].ls].sum,mid=(l+r)>>1; if (k<=sz) return query(t[rt].ls,l,mid,k); else return query(t[rt].rs,mid+1,r,k-sz); } inline void update(int rt,int l,int r,int opt,int x) { if (l==r) { if (opt==1) t[rt].sum++; if (opt==2&&t[rt].sum) t[rt].sum--; return ; } int mid=(l+r)>>1; if (x<=mid) update(t[rt].ls,l,mid,opt,x); else update(t[rt].rs,mid+1,r,opt,x); push_up(rt); return ; } inline void build(int rt,int l,int r) { if (l==r) { t[rt].sum=0; return ; } int mid=(l+r)>>1; t[rt].ls=++cnt; build(t[rt].ls,l,mid); t[rt].rs=++cnt; build(t[rt].rs,mid+1,r); return ; } int main() { freopen("page.in","r",stdin); freopen("page.out","w",stdout); int maxx=0; scanf("%d%d",&n,&k); for (int i=1;i<=n;i++) { scanf("%d",a+i); q[a[i]].push_back(i); maxx=max(a[i],maxx); } build(1,1,n+1); for (int i=1;i<=maxx;i++) q[i].push_back(n+1); for (int i=1;i<=n;i++) { int x=a[i]; if (!mark[x]) { if (t[1].sum<k) { while (q[x].front()<=i) q[x].pop_front(); update(1,1,n+1,1,q[x].front()); tp[q[x].front()]=x; mark[x]=1; } else { while (q[x].front()<=i&&!q[x].empty()) q[x].pop_front(); int now=query(1,1,n+1,t[1].sum); update(1,1,n+1,2,now); mark[tp[now]]=0; tp[now]=0; update(1,1,n+1,1,q[x].front()); tp[q[x].front()]=x; mark[x]=1; } ans++; } else { while (q[x].front()<=i&&!q[x].empty()) { update(1,1,n+1,2,q[x].front()); tp[q[x].front()]=0; q[x].pop_front(); } update(1,1,n+1,1,q[x].front()); tp[q[x].front()]=x; } } printf("%d\n",ans); return 0; }

考试时犯的错误:

*  最后一种情况双端队列弹反了
 *  想错数据范围，认为\\(a\_i<=n\\),所以导致预处理错误，以后预处理就按上面的方法了

\\(luogu\\)题目的代码

#include<iostream> #include<cstdio> #include<queue> using namespace std; const int N=1e5+100,M=5e5+100; struct Tree{ int ls,rs,sum; }t[M<<1]; deque<int>q[N]; int m,n,k,ans,cnt=1; int a[M],tp[M]; bool mark[M]; inline void push_up(int rt) { t[rt].sum=t[t[rt].ls].sum+t[t[rt].rs].sum; return ; } inline int query(int rt,int l,int r,int k) { if (l==r) return l; int sz=t[t[rt].ls].sum,mid=(l+r)>>1; if (k<=sz) return query(t[rt].ls,l,mid,k); else return query(t[rt].rs,mid+1,r,k-sz); } inline void update(int rt,int l,int r,int opt,int x) { if (l==r) { if (opt==1) t[rt].sum++; if (opt==2&&t[rt].sum) t[rt].sum--; return ; } int mid=(l+r)>>1; if (x<=mid) update(t[rt].ls,l,mid,opt,x); else update(t[rt].rs,mid+1,r,opt,x); push_up(rt); return ; } inline void build(int rt,int l,int r) { if (l==r) { t[rt].sum=0; return ; } int mid=(l+r)>>1; t[rt].ls=++cnt; build(t[rt].ls,l,mid); t[rt].rs=++cnt; build(t[rt].rs,mid+1,r); push_up(rt); return ; } int main() { int maxx=0; scanf("%d%d%d",&m,&k,&n); for (int i=1;i<=n;i++) { scanf("%d",a+i); maxx=max(a[i],maxx); q[a[i]].push_back(i); } build(1,1,n+1); for (int i=1;i<=maxx;i++) q[i].push_back(n+1); for (int i=1;i<=n;i++) { int x=a[i]; if (!mark[x]) { if (t[1].sum<k) { while (q[x].front()<=i) q[x].pop_front(); update(1,1,n+1,1,q[x].front()); tp[q[x].front()]=x; mark[x]=1; } else { while (q[x].front()<=i) q[x].pop_front(); int now=query(1,1,n+1,t[1].sum); update(1,1,n+1,2,now); mark[tp[now]]=0; tp[now]=0; update(1,1,n+1,1,q[x].front()); tp[q[x].front()]=x; mark[x]=1; } ans++; } else { while (q[x].front()<=i) { update(1,1,n+1,2,q[x].front()); tp[q[x].front()]=0; q[x].pop_front(); } update(1,1,n+1,1,q[x].front()); tp[q[x].front()]=x; } } printf("%d\n",ans); return 0; }

神奇的`multiset+vector`写法。

#include<iostream> #include<cstdio> #include<vector> #include<set> using namespace std; const int N=1e5+100,M=5e5+100; int n,k,p,ans; int a[M],tp[M]; bool mark[N]; vector<int>v[N]; multiset<int>s; int main() { scanf("%d%d%d",&n,&k,&p); int maxx=0; for (int i=1;i<=p;i++) { scanf("%d",a+i); v[a[i]].push_back(i); maxx=max(a[i],maxx); } for (int i=1;i<=maxx;i++) v[i].push_back(p+1); for (int i=1;i<=p;i++) { int x=a[i]; if (!mark[x]) { while (v[x][0]<=i) v[x].erase(v[x].begin(),v[x].begin()+1); if (int(s.size())<k) { s.insert(v[x][0]); tp[v[x][0]]=x; } else { set<int>::iterator it=s.end(); it--; mark[tp[*it]]=0; tp[*it]=0; s.erase(it); s.insert(v[x][0]); tp[v[x][0]]=x; } mark[x]=1; ans++; } else { while (v[x][0]<=i) { mark[tp[v[x][0]]]=0; tp[v[x][0]]=0; set<int>::iterator it=s.find(v[x][0]); if (it!=s.end()) s.erase(it); v[x].erase(v[x].begin(),v[x].begin()+1); } s.insert(v[x][0]); mark[x]=1; tp[v[x][0]]=x; } } printf("%d\n",ans); return 0; }

收获：

*  `deque`和`queue`不能像`vector<int>p[N]`这样使用，因为`deque`这样占用空间很大，\\(10^5\\)如果这样开需要\\(60-70M\\)的空间。
 *  `mutiset.erase()`，如果里面是迭代器只会删一个元素，如果是实值会全部删除
 *  平衡树一类的\\(STL\\),`--end()`是最大元素，`begin()`是最小的元素
 *  要分清\\(set\\)和\\(multiset\\)的特性

转载于:https://www.cnblogs.com/last-diary/p/11408057.html

[mg0M4I.png]: /images/20230601/cbaa9493347a4168b82cb8b450ad603d.png
[P3419 _POI2005_SAM-Toy Cars]: https://www.luogu.org/problem/P3419