首页 > 代码库 > BZOJ 1935: [Shoi2007]Tree 园丁的烦恼 [树状数组 离线 离散化]
BZOJ 1935: [Shoi2007]Tree 园丁的烦恼 [树状数组 离线 离散化]
传送门
刚才我还在郁闷网上怎么没人用$CDQ$分治做
突然发现根本没有时间序....
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>using namespace std;const int N=3e6+5;inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1; c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘; c=getchar();} return x*f;}int n,Q,c[N],mp[N];int m,qid;struct Operation{ int x,y,v,id; int qid,op; Operation():op(0){} Operation(int x,int y,int v,int id,int qid,int op): x(x),y(y),v(v),id(id),qid(qid),op(op){} bool operator <(const Operation &r)const{ return x==r.x?op<r.op:x<r.x; }}a[N];void devideQuery(){ int x1=read()-1,y1=read()-1,x2=read(),y2=read(); mp[++mp[0]]=y1;mp[++mp[0]]=y2; qid++; m++;a[m]=Operation(x2,y2,1,m,qid,1); m++;a[m]=Operation(x1,y2,-1,m,qid,1); m++;a[m]=Operation(x2,y1,-1,m,qid,1); m++;a[m]=Operation(x1,y1,1,m,qid,1);}void iniMP(){ sort(mp+1,mp+1+mp[0]); int p=0; mp[++p]=mp[1]; for(int i=2;i<=mp[0];i++) if(mp[i]!=mp[i-1]) mp[++p]=mp[i]; mp[0]=p;}int Bin(int v){ int l=1,r=mp[0]; while(l<=r){ int mid=(l+r)>>1; if(v==mp[mid]) return mid; else if(v<mp[mid]) r=mid-1; else l=mid+1; } return 0;}inline int lowbit(int x){return x&-x;}void add(int p,int v){for(;p<=n;p+=lowbit(p)) c[p]+=v;}int sum(int p){ int re=0; for(;p;p-=lowbit(p)) re+=c[p]; return re;}int ans[N];void solve(){ for(int i=1;i<=m;i++){ if(!a[i].op) add(a[i].y,1); else ans[a[i].qid]+=a[i].v*sum(a[i].y); } for(int i=1;i<=Q;i++) printf("%d\n",ans[i]);}int main(){ freopen("in","r",stdin); n=read();Q=read(); for(int i=1;i<=n;i++) a[++m].x=read(),mp[++mp[0]]=a[m].y=read(); for(int i=1;i<=Q;i++) devideQuery(); iniMP(); for(int i=1;i<=m;i++) a[i].y=Bin(a[i].y); sort(a+1,a+1+m); solve();}
BZOJ 1935: [Shoi2007]Tree 园丁的烦恼 [树状数组 离线 离散化]
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。