T到死。多了一个更新第一维的函数。多了一个logn的复杂度。
其实后来看了题解以后知道 更新一维可以直接在建立二维的时候就完成。再加入就是多此一举了。
其中的pushupy是多余的。。。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #define maxn 805 #define inf 0x3f3f3f3f using namespace std; int Min[maxn*3][maxn*3]; int Max[maxn*3][maxn*3]; int ansmin,ansmax; int n; inline int ReadInt() { char ch = getchar(); int data = 0; while (ch < ‘0‘ || ch > ‘9‘) { ch = getchar(); } do { data = data*10 + ch-‘0‘; ch = getchar(); }while (ch >= ‘0‘ && ch <= ‘9‘); return data; } inline void pushupx(int pos,int num) { Min[pos][num]=Min[pos][num<<1]>Min[pos][num<<1|1]?Min[pos][num<<1|1]:Min[pos][num<<1]; Max[pos][num]=Max[pos][num<<1]>Max[pos][num<<1|1]?Max[pos][num<<1]:Max[pos][num<<1|1]; } inline void pushupy(int pos,int num,int s,int e) { Min[pos][num]=Min[pos<<1][num]<Min[pos<<1|1][num]?Min[pos<<1][num]:Min[pos<<1|1][num]; Max[pos][num]=Max[pos<<1][num]>Max[pos<<1|1][num]?Max[pos<<1][num]:Max[pos<<1|1][num]; if(s==e) return; int mid=(s+e)>>1; pushupy(pos,num<<1,s,mid); pushupy(pos,num<<1|1,mid+1,e); } void buildx(int pos,int num,int s,int e,int rt) { if(s==e) { if(rt==-1){ int a; a=ReadInt(); Max[pos][num]=Min[pos][num]=a; } else { Min[pos][num]=min(Min[pos<<1][num],Min[pos<<1|1][num]); Max[pos][num]=max(Max[pos<<1][num],Max[pos<<1|1][num]); } return; } int mid=(s+e)>>1; buildx(pos,num<<1,s,mid,rt); buildx(pos,num<<1|1,mid+1,e,rt); pushupx(pos,num); } void buildy(int num,int s,int e) { if(s==e) { buildx(num,1,1,n,-1); return; } int mid=(s+e)>>1; buildy(num<<1,s,mid); buildy(num<<1|1,mid+1,e); buildx(num,1,1,n,1); } void queryx(int pos,int num,int s,int e,int l,int r) { if(l<=s && r>=e) { ansmin=Min[pos][num]<ansmin?Min[pos][num]:ansmin; ansmax=Max[pos][num]>ansmax?Max[pos][num]:ansmax; return ; } int mid=(s+e)>>1; if(r<=mid)queryx(pos,num<<1,s,mid,l,r); else if(l>mid)queryx(pos,num<<1|1,mid+1,e,l,r); else { queryx(pos,num<<1,s,mid,l,mid); queryx(pos,num<<1|1,mid+1,e,mid+1,r); } } void queryy(int num,int s,int e,int l,int r,int u,int d) { if(l<=s && r>=e) { queryx(num,1,1,n,u,d); return; } int mid=(s+e)>>1; if(r<=mid)queryy(num<<1,s,mid,l,r,u,d); else if(l>mid)queryy(num<<1|1,mid+1,e,l,r,u,d); else { queryy(num<<1,s,mid,l,mid,u,d); queryy(num<<1|1,mid+1,e,mid+1,r,u,d); } } void updatex(int pos,int num,int s,int e,int p,int val,int rt) { if(s==e) { if(rt!=-1){ Min[pos][num]=Max[pos][num]=val; } else { Min[pos][num]=min(Min[pos<<1][num],Min[pos<<1|1][num]); Max[pos][num]=max(Max[pos<<1][num],Max[pos<<1|1][num]); } return; } int mid=(s+e)>>1; if(p<=mid)updatex(pos,num<<1,s,mid,p,val,rt); else updatex(pos,num<<1|1,mid+1,e,p,val,rt); pushupx(pos,num); } void updatey(int num,int s,int e,int posy,int posx,int val) { if(s==e) { updatex(num,1,1,n,posx,val,1); return; } int mid=(s+e)>>1; if(posy<=mid)updatey(num<<1,s,mid,posy,posx,val); else updatey(num<<1|1,mid+1,e,posy,posx,val); updatex(num,1,1,n,posx,val,-1); } int main() { int T; T=ReadInt(); for(int cas=1;cas<=T;cas++) { printf("Case #%d:\n",cas); n=ReadInt(); buildy(1,1,n); int m; m=ReadInt(); while(m--) { int r,l,siz; r=ReadInt(); l=ReadInt(); siz=ReadInt(); siz/=2; int up,down,left,right; up=1>r-siz?1:r-siz; down=n<r+siz?n:r+siz; left=1>l-siz?1:l-siz; right=n<l+siz?n:l+siz; if(up>down) swap(up,down); if(left>right) swap(left,right); ansmin=inf; ansmax=-1; queryy(1,1,n,up,down,left,right); updatey(1,1,n,r,l,(ansmin+ansmax)/2); printf("%d\n",(ansmin+ansmax)/2); } } return 0; }
Python 字符串操作(string替换、删除、截取、复制、连接、比较、查找、包含、大小写转换、分割等),布布扣,bubuko.com