如果能够把所有区间内第二次出现某颜色的位置标记出来,树状数组查询一下就可以了。
考虑离线。按左端点从小到大排序,不断移动左端点并更新第二次出现的位置。
#include#include #include #include #include #include using namespace std;int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') { if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}#define N 2000010int n,m,c,a[N],nxt[N],p[N],tree[N],ans[N],flag[N];struct data{ int l,r,i; bool operator <(const data&a) const { return l q[i-1].l) add(nxt[q[i-1].l],-1),add(nxt[nxt[q[i-1].l]],1),q[i-1].l++; ans[q[i].i]=sum(q[i].r)-sum(q[i].l-1); } for (int i=1;i<=m;i++) printf("%d\n",ans[i]); return 0;}