记得3.13日我曾说过
【为什么我每天光搞这些东西
居然今天考试就用了。。
和那道题基本一样，就是要把树状数组换成二维的
【写完了之后造了点数据测了一下发现会T。。然后各种加优化还是会T一点点。。想着估计60分了，结果向总机子还快些，1.1秒就过了。。
YJP和G10似乎都是蒯的hzwer的
然后高一好多看过我blog的人似乎都蒯了我的
不过我也从hzwer那里蒯了个优化过来 虽然加了优化并没有变快
一开始自己写的，和上次那个思路一样，加了个没有询问的区间直接跳过的剪枝：
|
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 80 81 82 83 84 85 86 87 |
// <mat.cpp> - 03/23/16 08:21:06 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int getint(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } #define lowbit(x) ((x)&(-x)) const int MAX=320001; int n,q,tot; struct oper{ int x1,y1,x2,y2,k,s,got; bool tp; }op[MAX],opl[MAX],opr[MAX]; int ans[MAX]; int c[550][550]; inline void add(int x,int y,int k){ for(int X=x;X<=n;X+=lowbit(X)) for(int Y=y;Y<=n;Y+=lowbit(Y)) c[X][Y]+=k; } inline int ask(int x,int y){ int ans=0; for(int X=x;X;X-=lowbit(X)) for(int Y=y;Y;Y-=lowbit(Y)) ans+=c[X][Y]; return ans; } void divide(int top,int end,int l,int r){ if(top>end)return; if(l==r){ for(int i=top;i<=end;i++) if(op[i].tp)ans[op[i].s]=l; return; } int m=(l+r)>>1; int lo=0,ro=0; bool lc=0,rc=0; for(int i=top;i<=end;i++) if(op[i].tp){ int tmp=ask(op[i].x2,op[i].y2)+ask(op[i].x1-1,op[i].y1-1)-ask(op[i].x1-1,op[i].y2)-ask(op[i].x2,op[i].y1-1); if(op[i].got+tmp>=op[i].k){opl[++lo]=op[i];lc=1;} else {op[i].got+=tmp;opr[++ro]=op[i];rc=1;} }else{ if(op[i].k<=m){add(op[i].x1,op[i].y1,1);opl[++lo]=op[i];} else opr[++ro]=op[i]; } for(int i=top;i<=end;i++) if(!op[i].tp&&op[i].k<=m)add(op[i].x1,op[i].y1,-1); for(int i=1;i<=lo;i++)op[top+i-1]=opl[i]; for(int i=1;i<=ro;i++)op[top+lo+i-1]=opr[i]; if(lc)divide(top,top+lo-1,l,m); if(rc)divide(top+lo,end,m+1,r); } int main(){ freopen("mat.in","r",stdin); freopen("mat.out","w",stdout); n=getint(),q=getint(); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){ op[++tot].x1=i;op[tot].y1=j; op[tot].k=getint(); } for(int i=1;i<=q;i++){ op[++tot].x1=getint();op[tot].y1=getint(); op[tot].x2=getint();op[tot].y2=getint(); op[tot].k=getint(); op[tot].tp=1; op[tot].s=i; } divide(1,tot,0,1000000000); for(int i=1;i<=q;i++)printf("%d\n",ans[i]); return 0; } |
然后看了看hzwer写的，是先将数列排序，然后用一个T表示[0,T]区间内的数小于等于当前m，然后每次改T的范围，不清空树状数组。（好像也差不多）（似乎还是好一些）（但是Tsinsen上测出来一样快）
|
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 80 81 82 |
// <mat.cpp> - 03/23/16 08:21:06 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int getint(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } #define lowbit(x) ((x)&(-x)) const int MAX=260000; int n,q,tot,T; struct changes{ int x,y,k; bool operator < (const changes b) const {return k<b.k;} }cg[MAX]; struct oper{ int x1,y1,x2,y2,k,s; }op[MAX],opl[MAX],opr[MAX]; int ans[MAX]; int c[550][550]; inline void add(int X,int y,int k){ for(;X<=n;X+=lowbit(X)) for(int Y=y;Y<=n;Y+=lowbit(Y)) c[X][Y]+=k; } inline int ask(int X,int y){ int ans=0; for(;X;X-=lowbit(X)) for(int Y=y;Y;Y-=lowbit(Y)) ans+=c[X][Y]; return ans; } void divide(int top,int end,int l,int r){ if(top>end)return; if(l==r){ for(int i=top;i<=end;i++)ans[op[i].s]=l; return; } int m=(l+r)>>1; while(cg[T+1].k<=m&&T<tot){add(cg[T+1].x,cg[T+1].y,1);T++;} while(cg[T].k>m){add(cg[T].x,cg[T].y,-1);T--;} int lo=0,ro=0; for(int i = top;i <= end;i++){ int tmp=ask(op[i].x2,op[i].y2)+ask(op[i].x1-1,op[i].y1-1)-ask(op[i].x1-1,op[i].y2)-ask(op[i].x2,op[i].y1-1); if(tmp>=op[i].k)opl[++lo]=op[i]; else opr[++ro]=op[i]; } for(int i=1;i<=lo;i++)op[top+i-1]=opl[i]; for(int i=1;i<=ro;i++)op[top+lo+i-1]=opr[i]; if(lo)divide(top,top+lo-1,l,m); if(ro)divide(top+lo,end,m+1,r); } int main(){ n=getint(),q=getint(); for(int i = 1;i <= n;i++) for(int j=1;j<=n;j++){ cg[++tot].x=i;cg[tot].y=j; cg[tot].k=getint(); } sort(cg+1,cg+tot+1); for(int i=1;i<=q;i++){ op[i].x1=getint();op[i].y1=getint(); op[i].x2=getint();op[i].y2=getint(); op[i].k=getint(); op[i].s=i; } divide(1,q,cg[1].k,cg[tot].k); for(int i=1;i<=q;i++)printf("%d\n",ans[i]); return 0; } |
说点什么