【UOJ Round #8】

A

　　一道不错的题，虽然大家都觉得是水题，然而蒟蒻我想出来的好慢……Orz alpq

　　发现其实就是一个网格图，每一个大块都是同一颜色……横纵坐标互不干扰……

 1 //UOJ Round #8 A
 2 #include<vector>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<cstdlib>
 6 #include<iostream>
 7 #include<algorithm>
 8 #define rep(i,n) for(int i=0;i<n;++i)
 9 #define F(i,j,n) for(int i=j;i<=n;++i)
10 #define D(i,j,n) for(int i=j;i>=n;--i)
11 using namespace std;
12 typedef long long LL;
13 inline int getint(){
14     int r=1,v=0; char ch=getchar();
15     for(;!isdigit(ch);ch=getchar()) if (ch=='-') r=-1;
16     for(; isdigit(ch);ch=getchar()) v=v*10-'0'+ch;
17     return r*v;
18 }
19 const int N=1e5+10;
20 /*******************template********************/
21 
22 int n,m,x[N],y[N];
23 int bel1[N],bel2[N],cnt1,cnt2;
24 int main(){
25 #ifndef ONLINE_JUDGE
26     freopen("A.in","r",stdin);
27     freopen("A.out","w",stdout);
28 #endif 
29     n=getint(); m=getint();
30     F(i,1,n) x[i]=getint();
31     F(i,1,m) y[i]=getint();
32     int now=x[1];
33     bel1[1]=1; cnt1=1;
34     F(i,2,n){
35         if (x[i]!=now){
36             cnt1++;
37             now=x[i];
38         }
39         bel1[i]=cnt1;
40     }
41     now=y[1]; bel2[1]=1; cnt2=1;
42     F(i,2,m){
43         if (y[i]!=now){
44             cnt2++;
45             now=y[i];
46         }
47         bel2[i]=cnt2;
48     }
49 
50     int Q=getint();
51     F(i,1,Q){
52         int x1=getint(),y1=getint(),x2=getint(),y2=getint();
53         if (x2<x1) swap(x1,x2); if (y2<y1) swap(y1,y2);
54         int t1=min(bel1[x2]-bel1[x1],cnt1-bel1[x2]+bel1[x1]-(x[1]==x[n]));
55         int t2=min(bel2[y2]-bel2[y1],cnt2-bel2[y2]+bel2[y1]-(y[1]==y[m]));
56         printf("%d
",t1+t2);
57     }
58     return 0;
59 }

View Code

B

　　线段树的好题！（话说为什么我感觉那么像KD-Tree……

　　前两个操作就是普通线段树维护就可以……

　　查询的时候，感觉就是将n个点的横坐标固定成1~n了……然后用KD-Tree的估价函数来判断是否进入子树查询……

　　我一开始query写的逗比了，膜了一下vfk的姿势……

　　然后这题我TLE了好久……

　　重点是题解里说的：先判断右子树，再判断左子树！！！（就像KD-Tree的时候，要先像估价值较大的那一侧走啊！我怎么给忘了……sad

  1 //UOJ Round #8 B
  2 #include<vector>
  3 #include<cstdio>
  4 #include<cstring>
  5 #include<cstdlib>
  6 #include<iostream>
  7 #include<algorithm>
  8 #define rep(i,n) for(int i=0;i<n;++i)
  9 #define F(i,j,n) for(int i=j;i<=n;++i)
 10 #define D(i,j,n) for(int i=j;i>=n;--i)
 11 using namespace std;
 12 typedef long long LL;
 13 inline int getint(){
 14     int r=1,v=0; char ch=getchar();
 15     for(;!isdigit(ch);ch=getchar()) if (ch=='-') r=-1;
 16     for(; isdigit(ch);ch=getchar()) v=v*10-'0'+ch;
 17     return r*v;
 18 }
 19 const int N=1e5+10;
 20 /*******************template********************/
 21 
 22 int n,m,x0,v[N],mn[N<<2],mx[N<<2];
 23 bool rev[N<<2];
 24 inline int ran(){
 25     x0=((LL)x0*100000005+20150609)%998244353;
 26     return x0/100;
 27 }
 28 #define mid (l+r>>1)
 29 #define L (o<<1)
 30 #define R (o<<1|1)
 31 void maintain(int o,int l,int r){
 32     mn[o]=min(mn[L],mn[R]);
 33     mx[o]=max(mx[L],mx[R]);
 34 }
 35 void change(int o){
 36     rev[o]^=1;
 37     mn[o]=100000-mn[o]; mx[o]=100000-mx[o];
 38     swap(mn[o],mx[o]);
 39 }
 40 void Push_down(int o,int l,int r){
 41     if (rev[o]){
 42         change(L); change(R);
 43         rev[o]=0;
 44     }
 45 }
 46 void build(int o,int l,int r){
 47     if (l==r){
 48         mn[o]=mx[o]=ran()%100001;
 49     }else{
 50         build(L,l,mid);
 51         build(R,mid+1,r);
 52         maintain(o,l,r);
 53     }
 54 }
 55 void update(int o,int l,int r,int p,int val){
 56     if (l==r){
 57         mn[o]=mx[o]=val;
 58     }else{
 59         Push_down(o,l,r);
 60         if (p<=mid) update(L,l,mid,p,val);
 61         else update(R,mid+1,r,p,val);
 62         maintain(o,l,r);
 63     }
 64 }
 65 void modify(int o,int l,int r,int ql,int qr){
 66     if (ql<=l && qr>=r){
 67         change(o);
 68     }else{
 69         Push_down(o,l,r);
 70         if (ql<=mid) modify(L,l,mid,ql,qr);
 71         if (qr>mid) modify(R,mid+1,r,ql,qr);
 72         maintain(o,l,r);
 73     }
 74 }
 75 
 76 LL ans=0;
 77 int a,b,c;
 78 inline LL calc(int x,int y){return (LL)a*x+(LL)b*y+(LL)c*x*y;}
 79 void query(int o,int l,int r,int ql,int qr){
 80     if (calc(min(r,qr),mx[o])<=ans) return;
 81     if (l==r){
 82         ans=calc(l,mx[o]);
 83         return;
 84     }
 85     Push_down(o,l,r);
 86     if (qr>mid) query(R,mid+1,r,ql,qr);
 87     if (ql<=mid) query(L,l,mid,ql,qr);
 88 }
 89 
 90 int main(){
 91 #ifndef ONLINE_JUDGE
 92     freopen("B.in","r",stdin);
 93     freopen("B.out","w",stdout);
 94 #endif 
 95     n=getint(); m=getint(); x0=getint();
 96 //    F(i,1,n) v[i]=ran()%100001;
 97     build(1,1,n);
 98     char cmd;
 99     F(i,1,m){
100         while(cmd=getchar(),cmd!='C' && cmd!='R' && cmd!='Q');
101         if (cmd=='C'){
102             int p=ran()%n+1,y=ran()%100001;
103             update(1,1,n,p,y);
104         }else if (cmd=='R'){
105             int ql=ran()%n+1,qr=ran()%n+1;
106             if (qr<ql) swap(ql,qr);
107             modify(1,1,n,ql,qr);
108         }else if (cmd=='Q'){
109             a=getint(),b=getint(),c=getint();
110             int ql=ran()%n+1,qr=ran()%n+1;
111             if (qr<ql) swap(ql,qr);
112             ans=0;
113             query(1,1,n,ql,qr);
114             printf("%lld
",ans);
115         }
116     }
117     return 0;
118 }

View Code