# BZOJ2743 采花

n,m<=1000,000

### Solution

##### Code
#include<cstdio>
#include<algorithm>
using namespace std;
struct node{
int l,r,id;
}q[1000010];
int cnt=0;
int tree[8000010],pre[1000010],Pre[1000010],root[1000010],a[1000010],ans[1000010];
{
int ans=0;
char ch=getchar();
while (ch<'0'||ch>'9') ch=getchar();
while (ch>='0'&&ch<='9')
{
ans=ans*10+ch-'0';
ch=getchar();
}
return ans;
}
bool cmp(node x,node y)
{
return x.r<y.r;
}
void insert(int pos,int l,int r,int t,int key)
{
if (l==r)
{
tree[t]+=key;
return;
}
int mid=(l+r)>>1;
if (pos<=mid) insert(pos,l,mid,t<<1,key);
else insert(pos,mid+1,r,t<<1|1,key);
tree[t]=tree[t<<1]+tree[t<<1|1];
}
int query(int t,int l,int r,int x,int y)
{
if (!tree[t]) return 0;
if (l==x&&y==r) return tree[t];
int mid=(l+r)>>1;
if (y<=mid) return query(t<<1,l,mid,x,y);
if (x>mid) return query(t<<1|1,mid+1,r,x,y);
return query(t<<1,l,mid,x,mid)+query(t<<1|1,mid+1,r,mid+1,y);
}
int main()
{
int n,c,m;
scanf("%d%d%d",&n,&c,&m);
for (int i=1;i<=m;i++)
sort(q+1,q+1+m,cmp);
for (int i=1;i<=n;i++)
{
if (Pre[pre[a[i]]]) insert(Pre[pre[a[i]]],1,n,1,-1);
if (pre[a[i]]) insert(pre[a[i]],1,n,1,1);