CIA9 彩色弹珠

CIA9 彩色弹珠

​​ 题目背景

2017.11.8

leoly选讲题

题目描述

玩具店新开张，免费赠送一些彩色弹珠，小明决定来蹭这个便宜。

玩具店老板将

n

n个弹珠排成了一排，第

i

i个弹珠有一个颜色

c_i

ci。小明只能从这排弹珠里选取一个区间，拿到其中仅出现了该颜色一次的弹珠。

小明想知道他最多可以拿走几颗弹珠。

输入输出格式

输入格式：

第一行一个正整数

n

n，表示有

n

n个弹珠。第二行

n

n个数用空格隔开，第

i

i个数表示弹珠颜色

c_i

ci。

输出格式：

一个数，表示小明最多能拿走的弹珠数量。

输入输出样例

输入样例#1： 复制

10 1 2 3 6 6 3 7 9 8 8 输出样例#1： 复制

5 说明

对于

30\%

30%的数据：

n \leq 1000

n≤1000。

对于

100\%

100%的数据：

n \leq 300000

n≤300000，

1 \leq c_i \leq n

1≤ci≤n。

时间限制：

1000ms

1000ms。

内存限制：

256MB

256MB。

预处理出每个点的前缀&后缀

那么在他们的前缀和后缀之间的就是都可以取的

所以我们认为可以构造这样一个区间 左端点属于pre[i]+1～i 右端点属于i～last[i]-1 这样的区间 都可以享受到来自a[i]的加成

那么我们可以利用之前扫面线一样 我们把区间的两个端点看做平面上的点

然后相当于每次一个矩形 然后求问 平面内 哪个点被矩形覆盖的次数最多 求出这个次数是多少即可 相当于差不多是询问离线 然后线段树维护即可

#include#include#includeusing namespace std;#define N 330000#define inf 0x7f7f7f7finline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0;char ch=gc(); while (ch<'0'||ch>'9') ch=gc(); while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=gc();} return x;}struct node{ int x,y1,y2,op;}qr[N<<1];int num;struct node1{ int left,right,max,lazy;}tree[N<<2];inline bool cmp(node a,node b){ return a.x=r) {tree[x].lazy+=v;tree[x].max+=v;return;} int mid=l+r>>1;pushdown(x); if (l1<=mid) insert1(tree[x].left,l,mid,l1,r1,v); if (r1>mid) insert1(tree[x].right,mid+1,r,l1,r1,v); update(x);}int n,b[N],a[N],pre[N],last[N];int main(){ //freopen("16745.in","r",stdin); n=read();memset(b,0x7f,sizeof(b)); for (int i=1;i<=n;++i) a[i]=read(); for (int i=1;i<=n;++i){ pre[i]=b[a[i]]!=inf?b[a[i]]+1:inf;b[a[i]]=i; }memset(b,0x7f,sizeof(b)); for (int i=n;i>=1;--i){ last[i]=b[a[i]]!=inf?b[a[i]]-1:inf;b[a[i]]=i; }int tot=0; //for (int i=1;i<=n;++i) printf("%d %d\n",pre[i],last[i]); for (int i=1;i<=n;++i){ qr[++tot].x=pre[i];qr[tot].y1=i;qr[tot].y2=last[i];qr[tot].op=1;if (qr[tot].x==inf) qr[tot].x=1;if (qr[tot].y2==inf) qr[tot].y2=n; qr[++tot].x=i+1;qr[tot].y1=i;qr[tot].y2=last[i];qr[tot].op=-1;if (qr[tot].y2==inf) qr[tot].y2=n; } //tree[0].left=tree[0].right= sort(qr+1,qr+tot+1,cmp);int cnt=1,root=0;int ans=0; //for (int i=1;i<=tot;++i) printf("%d %d %d %d\n",qr[i].x,qr[i].y1,qr[i].y2,qr[i].op); for (int j=1;j<=n;++j){ while (qr[cnt].x==j&&cnt<=tot){ insert1(root,1,n,qr[cnt].y1,qr[cnt].y2,qr[cnt].op); //if (tree[root].max==22539) printf("%d %d %d\n",qr[cnt].x,qr[cnt].y1,qr[cnt].y2); ++cnt; } ans=max(ans,tree[root].max); } printf("%d\n",ans); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。