貌似比在線快很多。

看大佬怎么離線的才學(xué)會離線的，注意a[i].f=1,0,2的順序不能混，為什么寫一組數(shù)據(jù)一看就知道了。

#include<bits/stdc++.h>
using namespace std;
const int  maxn=1e5+10;
int sum[4*maxn],ans1[maxn],ans2[maxn];
struct node
{int l,r;
}t[4*maxn];
struct node2
{int l,r,p,v,f;
}a[4*maxn];
bool cmp(node2 x,node2 y)
{if(x.v==y.v)return x.f<y.f;else return x.v<y.v;
}
void build(int rt,int l,int r)
{t[rt].l=l;t[rt].r=r;if(t[rt].l==t[rt].r)return ;int mid=(l+r)>>1; build(rt<<1,l,mid);build(rt<<1|1,mid+1,r);
}
void pushup(int rt)
{sum[rt]=sum[rt<<1]+sum[rt<<1|1];  
}
void update(int p,int rt,int l,int r)
{if(l==r){sum[rt]++;return ;}int mid=(l+r)>>1;if(p>mid)update(p,rt<<1|1,mid+1,r);else update(p,rt<<1,l,mid); pushup(rt);
}
int  query(int l,int r,int u)
{if(t[u].l>=l&&t[u].r<=r){   return sum[u]; }int mid=(t[u].l+t[u].r)/2;int res=0;if(mid>=l)res+=query(l,r,u<<1);if(r>mid) res+=query(l,r,u<<1|1); return res;
}
int main()
{int n,m;while(~scanf("%d %d",&n,&m)){build(1,1,n);for(int i=1;i<=n;i++){scanf("%d",&a[i].v);a[i].f=1;a[i].p=i;}int cnt=n;for(int i=1;i<=m;i++){int tmp=2*i-1;scanf("%d%d%d%d",&a[cnt+tmp].l,&a[cnt+tmp].r,&a[cnt+tmp].v,&a[cnt+tmp+1].v);a[cnt+tmp+1].l=a[cnt+tmp].l;a[cnt+tmp+1].r=a[cnt+tmp].r;a[cnt+tmp].f=0;a[cnt+1+tmp].f=2;a[cnt+tmp].p=a[cnt+tmp+1].p=i; }cnt+=2*m;sort(a+1,a+1+cnt,cmp);for(int i=1;i<=cnt;i++){if(a[i].f==1) update(a[i].p,1,1,n);else if(a[i].f==0) ans1[a[i].p]=query(a[i].l,a[i].r,1);else ans2[a[i].p]=query(a[i].l,a[i].r,1);}for(int i=1;i<=m;i++){printf("%d\n",ans2[i]-ans1[i]);}}}

總結(jié)

以上是生活随笔為你收集整理的xdoj 1114（线段树离线处理）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。