tyvj4866 摆摊

tyvj4866 摆摊

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

90分代码：

#include<bits/stdc.h>
using namespace std;
#define MAX 100000010
struct que{int l,r,id,a1,a2;}qu[MAX];
int n,m,siz,q,a[MAX],pos[MAX],vis[MAX];
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=1;i<=m;i)scanf(%d,&a[i]);for(int i=1;i<=q;i)scanf(%d%d,&qu[i].l,&qu[i].r),qu[i].id=i;for(int i=1;i<=m;i)pos[i]=(i-1)/siz1;sort(qu1,quq1,cmp);for(int i=qu[1].l;i<=qu[1].r;i)vis[a[i]];int l=qu[1].l,r=qu[1].r;for(int i=1;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=-1;for(int j=1;j<n;j)if(!vis[j]&&!vis[j1]){qu[qu[i].id].a1=j;qu[qu[i].id].a2=j1;break;}}for(int i=1;i<=q;i)if(qu[i].a1==-1)printf(-1\n);else printf(%d %d\n,qu[i].a1,qu[i].a2);return 0;
}

主席树正解的坑有空再填

转载于:.html