作业

思路

然而并没有题面,2333

莫队+树状数组,20s稳得很…..

代码

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>
#define N 210010
#define M 1500000
using namespace std;
int n,m,block;
int f[N],a[N],itc[N];
int num[N],t[N];
int ans[M][2];
int read()
{
    int out=0,flag=1;
    char c=getchar();
    while(c<48||c>57) {if(c=='-') flag=-1;c=getchar();}
    while(c>=48&&c<=57)
    {
        out=out*10+c-48;
        c=getchar();
    }
    return out*flag;
}
struct node
{
	int l,r,a,b,id;
}ask[M];
bool comp(node aa,node bb)
{
	return itc[aa.l]==itc[bb.l]? aa.r<bb.r:itc[aa.l]<itc[bb.l];
}
bool cmp(node aa,node bb)
{
	return aa.id<bb.id;
}
void ADD(int now,int it,int at[])
{
	for(int i=now;i<=n;i+=(i&(-i)))
	{
		at[i]+=it;
	}
}
void add(int now)
{
	if(!num[now]) ADD(now,1,t);
	num[now]++;
	ADD(now,1,f);
}
void pop(int now)
{
	num[now]--;
	if(!num[now]) ADD(now,-1,t);
	ADD(now,-1,f);
}
int Ask(int now,int at[])
{
	if(now<1)return 0;
	int re=0;
	for(int i=now;i;i-=(i&(-i)))
	{
		re+=at[i];
	}
	return re;
}
int main()
{
	freopen("ahoi2013_homework.in","r",stdin);
	freopen("ahoi2013_homework.out","w",stdout);
	n=read();m=read();
	block=sqrt(n);
	for(int i=1;i<=n;++i)
	{
		a[i]=read();
		itc[i]=(i-1)/block+1;
	}
	for(int i=1;i<=m;++i)
		ask[i].l=read(),ask[i].r=read(),ask[i].a=read(),ask[i].b=read(),ask[i].id=i;
	sort(ask+1,ask+m+1,comp);
	int L=ask[1].l,R=ask[1].r;
	for(int i=L;i<=R;++i) 
	{
		add(a[i]);
	}
	ans[ask[1].id][0]=Ask(ask[1].b,f)-Ask(ask[1].a-1,f);
	ans[ask[1].id][1]=Ask(ask[1].b,t)-Ask(ask[1].a-1,t);
	for(int i=2;i<=m;++i)
	{
		while(R<ask[i].r) add(a[++R]);
		while(R>ask[i].r) pop(a[R--]);
		while(L<ask[i].l) pop(a[L++]);
		while(L>ask[i].l) add(a[--L]);
		ans[ask[i].id][0]=Ask(ask[i].b,f)-Ask(ask[i].a-1,f);
	    ans[ask[i].id][1]=Ask(ask[i].b,t)-Ask(ask[i].a-1,t);
    }
	for(int i=1;i<=m;++i)
	{
		printf("%d %d\n",ans[i][0],ans[i][1]);
	}
	return 0;
}
(update the code to your comment plugin in comment-full.html)