1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79
| #include<cstdio> #include<iostream> #include<algorithm> using namespace std; int read() { char c=getchar();int x=0;bool f=0; for(;!isdigit(c);c=getchar())f^=!(c^45); for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48); if(f)x=-x;return x; } int n,m,p,t,a[500001],b[500001],c[500001],rt[500001]; struct tree { int l,r,s; }T[30000001]; void pushup(int x) { T[x].s=T[T[x].l].s+T[T[x].r].s; } void build(int &x,int l,int r) { x=++p; if(l==r) return; int z=l+r>>1; build(T[x].l,l,z); build(T[x].r,z+1,r); } void modify(int &x,int l,int r,int q) { T[++p]=T[x]; ++T[p].s; x=p; if(l==r) return; int z=l+r>>1; if(q<=z) modify(T[x].l,l,z,q); else modify(T[x].r,z+1,r,q); } int num(int x,int l,int r,int k) { if(l==r) return 0; int z=l+r>>1; if(k==z) return T[T[x].l].s; if(k<z) return num(T[x].l,l,z,k); return T[T[x].l].s+num(T[x].r,z+1,r,k); } int main() { freopen("stack.in","r",stdin); freopen("stack.out","w",stdout); n=read(),m=read(); for(int i=1;i<=n;++i) a[i]=read(); for(int i=1;i<=n;++i) b[i]=read(); a[0]=0; b[0]=1e9; c[0]=0; build(rt[0],0,n); for(int i=1;i<=n;++i) { int l=0,r=t,z; while(l<r) { z=(l+r+1)>>1; if(b[i]<b[c[z]]) l=z; else r=z-1; } while(a[c[l]]==a[i]) --l; t=l+1; c[t]=i; rt[i]=rt[i-1]; modify(rt[i],0,n,c[l]); } for(int i=1;i<=m;++i) { int l=read(),r=read(); printf("%d\n",num(rt[r],0,n,l-1)-num(rt[l-1],0,n,l-1)); } return 0; }
|