tyvj4866 摆摊

这分送的真慷慨，我随手打了个莫队，就90了。。。。

90分代码：

#include<bits/stdc++.h>

using namespace std;

#define MAXN 1000000+10

struct que{int l,r,id,a1,a2;}qu[MAXN];

int n,m,siz,q,a[MAXN],pos[MAXN],vis[MAXN];

bool cmp(que a,que b){return pos[a.l]==pos[b.l]?a.r<b.r:pos[a.l]<pos[b.l];}

int main(){

    scanf("%d%d%d",&n,&m,&q);

    siz=sqrt(m);

    for(int i=;i<=m;i++)scanf("%d",&a[i]);

    for(int i=;i<=q;i++)scanf("%d%d",&qu[i].l,&qu[i].r),qu[i].id=i;

    for(int i=;i<=m;i++)pos[i]=(i-)/siz+;

    sort(qu+,qu+q+,cmp);

    for(int i=qu[].l;i<=qu[].r;i++)vis[a[i]]++;

    int l=qu[].l,r=qu[].r;

    for(int i=;i<=q;i++){

        while(l<qu[i].l)vis[a[l]]--,l++;

        while(r>qu[i].r)vis[a[r]]--,r--;

        while(l>qu[i].l)l--,vis[a[l]]++;

        while(r<qu[i].r)r++,vis[a[r]]++;

        qu[qu[i].id].a1=-;

        for(int j=;j<n;j++)

            if(!vis[j]&&!vis[j+]){

                qu[qu[i].id].a1=j;

                qu[qu[i].id].a2=j+;

                break;

            }

    }

    for(int i=;i<=q;i++)

        if(qu[i].a1==-)printf("-1\n");

        else printf("%d %d\n",qu[i].a1,qu[i].a2);

    return ;

}

主席树正解的坑有空再填

相关文章