【bzoj3236】[Ahoi2013]作业

2015.05.01 14:48 Fri | 20次阅读 | 旧日oi | 固定链接 | 源码

Description

.jpg)

Input

Output

Sample Input

3 4
1 2 2
1 2 1 3
1 2 1 1
1 3 1 3
2 3 2 3

Sample Output

2 2
1 1
3 2
2 1

HINT

N=100000,M=1000000

题解

莫队算法+两个树状数组,没什么难的

我的程序

#include <bits/stdc++.h>
using namespace std;
#define maxn 100005
int n,q,m,block,pos[maxn],b[maxn],c[maxn];
int ans1[1000005],ans2[1000005];
struct Que
{
    int l,r,a,b,id;
}a[1000005];
bool cmp(const Que &a,const Que &b)
{
    if(pos[a.l]==pos[b.l]) return a.r<b.r;
    return a.l<b.l;
}
int c1[maxn],c2[maxn];
int lowbit(int x)
{
    return x&(-x);
}
void add1(int x,int num)
{
    for(;x<=n;x+=lowbit(x)) c1[x]+=num;
}
void add2(int x,int num)
{
    for(;x<=n;x+=lowbit(x)) c2[x]+=num;
}
int query1(int x)
{
    int ret=0;
    for(;x;x-=lowbit(x)) ret+=c1[x];
    return ret;
}
int query2(int x)
{
    int ret=0;
    for(;x;x-=lowbit(x)) ret+=c2[x];
    return ret;
}
void update(int x,int add)
{
    if(add==1)
    {
        if(!c[b[x]]) add2(b[x],1);
        c[b[x]]++;add1(b[x],1);
    }
    else
    {
        c[b[x]]--;add1(b[x],-1);
        if(!c[b[x]]) add2(b[x],-1);
    }
}
int main()
{
    cin>>n>>q;block=int(sqrt(n));
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&b[i]);
        pos[i]=(i-1)/block+1;
    }
    for(int i=1;i<=q;i++)
    {
        scanf("%d%d%d%d",&a[i].l,&a[i].r,&a[i].a,&a[i].b);
        a[i].id=i;
    }
    sort(a+1,a+q+1,cmp);
    for(int l=1,r=0,i=1;i<=q;i++)
    {
        if(a[i].a>a[i].b) continue;
        while(l<a[i].l) update(l,-1),l++;
        while(l>a[i].l) update(l-1,1),l--;
        while(r>a[i].r) update(r,-1),r--;
        while(r<a[i].r) update(r+1,1),r++;
        ans1[a[i].id]=query1(a[i].b)-query1(a[i].a-1);
        ans2[a[i].id]=query2(a[i].b)-query2(a[i].a-1);
    }
    for(int i=1;i<=q;i++) printf("%d %d\n",ans1[i],ans2[i]);
}```