A
一道不错的题，虽然大家都觉得是水题，然而蒟蒻我想出来的好慢……Orz alpq
发现其实就是一个网格图，每一个大块都是同一颜色……横纵坐标互不干扰……
//UOJ Round #8 A
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
using namespace std;
typedef long long LL;
inline int getint(){
int r=,v=; char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if (ch=='-') r=-;
for(; isdigit(ch);ch=getchar()) v=v*-''+ch;
return r*v;
}
const int N=1e5+;
/*******************template********************/ int n,m,x[N],y[N];
int bel1[N],bel2[N],cnt1,cnt2;
int main(){
#ifndef ONLINE_JUDGE
freopen("A.in","r",stdin);
freopen("A.out","w",stdout);
#endif
n=getint(); m=getint();
F(i,,n) x[i]=getint();
F(i,,m) y[i]=getint();
int now=x[];
bel1[]=; cnt1=;
F(i,,n){
if (x[i]!=now){
cnt1++;
now=x[i];
}
bel1[i]=cnt1;
}
now=y[]; bel2[]=; cnt2=;
F(i,,m){
if (y[i]!=now){
cnt2++;
now=y[i];
}
bel2[i]=cnt2;
} int Q=getint();
F(i,,Q){
int x1=getint(),y1=getint(),x2=getint(),y2=getint();
if (x2<x1) swap(x1,x2); if (y2<y1) swap(y1,y2);
int t1=min(bel1[x2]-bel1[x1],cnt1-bel1[x2]+bel1[x1]-(x[]==x[n]));
int t2=min(bel2[y2]-bel2[y1],cnt2-bel2[y2]+bel2[y1]-(y[]==y[m]));
printf("%d\n",t1+t2);
}
return ;
}
B
线段树的好题！（话说为什么我感觉那么像KD-Tree……
前两个操作就是普通线段树维护就可以……
查询的时候，感觉就是将n个点的横坐标固定成1~n了……然后用KD-Tree的估价函数来判断是否进入子树查询……
我一开始query写的逗比了，膜了一下vfk的姿势……
然后这题我TLE了好久……
重点是题解里说的：先判断右子树，再判断左子树！！！（就像KD-Tree的时候，要先像估价值较大的那一侧走啊！我怎么给忘了……sad
//UOJ Round #8 B
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
using namespace std;
typedef long long LL;
inline int getint(){
int r=,v=; char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if (ch=='-') r=-;
for(; isdigit(ch);ch=getchar()) v=v*-''+ch;
return r*v;
}
const int N=1e5+;
/*******************template********************/ int n,m,x0,v[N],mn[N<<],mx[N<<];
bool rev[N<<];
inline int ran(){
x0=((LL)x0*+)%;
return x0/;
}
#define mid (l+r>>1)
#define L (o<<1)
#define R (o<<1|1)
void maintain(int o,int l,int r){
mn[o]=min(mn[L],mn[R]);
mx[o]=max(mx[L],mx[R]);
}
void change(int o){
rev[o]^=;
mn[o]=-mn[o]; mx[o]=-mx[o];
swap(mn[o],mx[o]);
}
void Push_down(int o,int l,int r){
if (rev[o]){
change(L); change(R);
rev[o]=;
}
}
void build(int o,int l,int r){
if (l==r){
mn[o]=mx[o]=ran()%;
}else{
build(L,l,mid);
build(R,mid+,r);
maintain(o,l,r);
}
}
void update(int o,int l,int r,int p,int val){
if (l==r){
mn[o]=mx[o]=val;
}else{
Push_down(o,l,r);
if (p<=mid) update(L,l,mid,p,val);
else update(R,mid+,r,p,val);
maintain(o,l,r);
}
}
void modify(int o,int l,int r,int ql,int qr){
if (ql<=l && qr>=r){
change(o);
}else{
Push_down(o,l,r);
if (ql<=mid) modify(L,l,mid,ql,qr);
if (qr>mid) modify(R,mid+,r,ql,qr);
maintain(o,l,r);
}
} LL ans=;
int a,b,c;
inline LL calc(int x,int y){return (LL)a*x+(LL)b*y+(LL)c*x*y;}
void query(int o,int l,int r,int ql,int qr){
if (calc(min(r,qr),mx[o])<=ans) return;
if (l==r){
ans=calc(l,mx[o]);
return;
}
Push_down(o,l,r);
if (qr>mid) query(R,mid+,r,ql,qr);
if (ql<=mid) query(L,l,mid,ql,qr);
} int main(){
#ifndef ONLINE_JUDGE
freopen("B.in","r",stdin);
freopen("B.out","w",stdout);
#endif
n=getint(); m=getint(); x0=getint();
// F(i,1,n) v[i]=ran()%100001;
build(,,n);
char cmd;
F(i,,m){
while(cmd=getchar(),cmd!='C' && cmd!='R' && cmd!='Q');
if (cmd=='C'){
int p=ran()%n+,y=ran()%;
update(,,n,p,y);
}else if (cmd=='R'){
int ql=ran()%n+,qr=ran()%n+;
if (qr<ql) swap(ql,qr);
modify(,,n,ql,qr);
}else if (cmd=='Q'){
a=getint(),b=getint(),c=getint();
int ql=ran()%n+,qr=ran()%n+;
if (qr<ql) swap(ql,qr);
ans=;
query(,,n,ql,qr);
printf("%lld\n",ans);
}
}
return ;
}