admin管理员组

文章数量:1026989

中山纪中集训游记Day2+8.2模拟赛题解

Part.I游记

纪中的OJ真的。。。今天下午又炸一次。。。

今天模拟赛竟然是考的集训队互测的题。。。做到自闭。。。

一开考看见第一题，给我的感觉是要写树套树。。。然而我不想写。。。

然后就去看了第二题，看上去要用矩阵乘法。什么期望题啊，我写不来。。。（我矩乘都要忘完了。。。

看了看第三题，目测可用线段树解决。先打一发暴力再说。

这时机房里的某位同学因为上网干一些hhh的事情，被老师发现了，然后，机房的网就断了。。。

我开始写60分的做法（ O ( N 2 log ⁡ 2 N ) O(N^2\log_2N) O(N2log2​N)）然而我写的可持久化线段树炸了。。。调了半天勉强过样例。我写了个数据生成器和暴力程序对拍，结果才一组就挂了。。。

然后我就自闭了。。。

下午听讲题，讲题人讲到第一题暴力可过，因为第一题的时限是10s。。。F**k还是怪自己不够仔细。。。

第二题真的是用矩乘。。。然而考场上的我去做第三题了。。。

第三题我听的时候猛然发现我推的做法和题解相差不大。。。但是题解普通线段树解决的我为什么偏要写可持久化。。。(逃

最后只有30分。。。

Prat.II题解

A.【集训队互测 2012】Attack

题目

题目描述

chnlich 非常喜欢玩三国志这款游戏,并喜欢用一些策略出奇制胜。现在,他要开始征服世界的旅途了。他的敌人有N 座城市和N 个太守, N个城市可以看作在二维平面上的N 个点。N 座城市的标号为0,1,2,…,N-1。第i 座城市的坐标为(Xi,Yi),镇守这座城市的太守的能力值为Zi。

chnlich 每次会选择一个边平行于坐标轴的矩形区域,并奇袭其中太守能力值第K小的城市(奇袭结束之后城市与太守依然存在)。

不过,他的敌人经常会偷偷交换两座城市的太守,防止弱点被chnlich 发现。

现在,chnlich 想要知道,每次奇袭时他的敌人的能力值。

输入

输入的第一行包含两个整数 N,M,N 表示城市与太守的个数,M 表示接下来发生了 M 个事件。

输入的第二行到第 N+1行,每行包含三个整数,第 i+2行的三个整数依次表示编号为 i 的城市的 Xi,Yi,Zi,含义如题所述。

输入的第 N+2行到第 N+M+1行,每行有两种可能形式:

第一种

QUERY x0 y0 x1 y1 k

表示 chnlich 询问一个相对顶点为(x0,y0),(x1,y1)的矩形中,第 k 小能力值太

守的能力值。

第二种

SWAP x y

表示 chnlich 的敌人交换了编号为 x 和 y 两座城市的太守。

输出

对于每一个 QUERY,输出一行。

若不存在第 k 小能力值的太守,输出"It doesn’t exist."(不包含引号)。

否则输出一个整数,表示矩形内能力值第 k 小太守的能力值。

样例输入

3 5
1 1 1
2 2 2
3 3 3
QUERY 1 1 3 3 3
SWAP 0 1
QUERY 2 2 4 4 1
SWAP 2 2
QUERY 2 2 3 3 3

样例输出

3
1
It doesn’t exist.

数据范围

对于100%的数据, N ≤ 60000 , M ≤ 10000 , 0 ≤ X i , Y i , Z i ≤ 1 0 9 , k ≤ 1 0 9 N\le60000,M\le10000,0\le Xi,Yi,Zi\le10^9,k\le10^9 N≤60000,M≤10000,0≤Xi,Yi,Zi≤109,k≤109,保证所有操作均合法。

分析

纪中OJ的机器跑得真快，暴力跑得比标程快。。。（这玩意只跑了3.7s！！！

正解说要用什么划分树之类的东西（反正我不会。。。

参考代码

#include<cstdio>
#include<algorithm>
using namespace std;const int Maxn=600000;int N;
struct Point {int x,y;int z;
};
Point A[Maxn+5];
bool cmp(int lhs,int rhs) {return A[lhs].z<A[rhs].z;
}
int rnk[Maxn+5],pos[Maxn+5];int main() {#ifdef LOACLfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifint Q;scanf("%d %d",&N,&Q);for(int i=1;i<=N;i++) {scanf("%d %d %d",&A[i].x,&A[i].y,&A[i].z);rnk[i]=i;}sort(rnk+1,rnk+N+1,cmp);for(int i=1;i<=N;i++)pos[rnk[i]]=i;while(Q--) {char s[10];scanf("%s",s);if(s[0]=='S') {int a,b;scanf("%d %d",&a,&b);a++,b++;swap(rnk[pos[a]],rnk[pos[b]]),swap(A[a].z,A[b].z),swap(pos[a],pos[b]);} else {int cnt=0,x1,y1,x2,y2,k;scanf("%d %d %d %d %d",&x1,&y1,&x2,&y2,&k);if(x1>x2)swap(x1,x2);if(y1>y2)swap(y1,y2);bool flag=false;for(int i=1;i<=N&&cnt<k;i++)if(x1<=A[rnk[i]].x&&A[rnk[i]].x<=x2&&y1<=A[rnk[i]].y&&A[rnk[i]].y<=y2) {cnt++;if(cnt==k) {flag=true;printf("%d\n",A[rnk[i]].z);break;}}if(flag==false)puts("It doesn't exist.");}}return 0;
}

B.【集训队互测 2012】Contra

题目

题目描述

偶然间,chnlich 发现了他小时候玩过的一个游戏“魂斗罗”,于是决定怀旧。但是这是一个奇怪的魂斗罗 MOD。

有 N 个关卡,初始有 Q 条命。

每通过一个关卡,会得到 u 分和1条命,生命上限为 Q。其中 u=min(最近一次连续通过的关数,R)。

若没有通过这个关卡,将会失去1条命,并进入下一个关卡。

当没有生命或没有未挑战过的关卡时,游戏结束,得到的分数为每关得到的分数的总和。

由于 chnlich 好久不玩这个游戏了,每条命通过每个关卡的概率均为p(0<=p<=1),原先 chnlich 的最高分纪录是 S。

现在 chnlich 想要知道,当 p 至少为多少时,chnlich 期望获得的总分数能够超过原先的最高分。

输入

输入共一行,分别表示整数 N,整数 R,整数 Q,原先的最高分整数 S。

输出

输出共一行,若不存在这样的 p,输出"Impossible."(不包含引号),否则输出 p(保留6位小数)。

样例输入

【样例输入一】
4 2 1 5
【样例输入二】
12 3 2 12

样例输出

【样例输出一】
0.880606
【样例输出二】
0.687201

【数据说明】

对于20%的数据,N<=15

对于50%的数据,N<=10000

对于100%的数据,N<=10^8,1<=R<=20,1<=Q<=5,保证 S 是一个可能出现的分数。

【补充说明】

例如,当 N=12,R=3,Q=2时

第一关:未通过 u=0 获得分数0 总分为0 剩余生命1

第二关:通过 获得分数1 总分为1 剩余生命2

第三关:通过 获得分数2 总分为3 剩余生命2

第四关:通过 获得分数3 总分为6 剩余生命2

第五关:通过 获得分数3 总分为9 剩余生命2

第六关:未通过 获得分数0 总分为9 剩余生命1

第七关:通过 获得分数1 总分为10 剩余生命2

第八关:未通过 获得分数0 总分为10 剩余生命1

第九关:未通过 获得分数0 总分为10 剩余生命0

游戏结束 总分为10

这是 chnlich 游戏的一种可能性

分析

显然我们需要二分答案。

我们二分出一个答案 P P P，那我们如何去检验这个答案。一个显而易见的方案是做一个DP。

不难发现当前能否继续走下去和得分只和命数和连胜的关卡数有关，所以，我们设计一个这样的DP状态：

我们设 f [ i ] [ j ] [ k ] , g [ i ] [ j ] [ k ] f[i][j][k],g[i][j][k] f[i][j][k],g[i][j][k]为当前剩余 i i i条命，已经连胜 j j j关，过了 k k k关的概率和得分，状态转移方程式非常好列，那么总的数学期望就是 ∑ i = 1 n f [ 0 ] [ 0 ] [ i ] × g [ 0 ] [ 0 ] [ i ] + ∑ i = 1 Q ∑ i = 1 R f [ i ] [ j ] [ N ] × g [ i ] [ j ] [ N ] \sum_{i=1}^{n}{f[0][0][i]\times g[0][0][i]}+\sum_{i=1}^{Q}{\sum_{i=1}^{R}{f[i][j][N]\times g[i][j][N]}} ∑i=1n​f[0][0][i]×g[0][0][i]+∑i=1Q​∑i=1R​f[i][j][N]×g[i][j][N]。

但这需要两个数组，而矩乘只能有一个。我们必须重新定义状态。

不难发现，边DP边算得分其实是不必要的，我们最后计算得分其实也是可以的，所以我们只需求概率即可。

设 g [ i ] [ j ] [ k ] g[i][j][k] g[i][j][k]为当前剩余 i i i条命，已经连胜 j j j关，过了 k k k关的概率。

列出 g g g的状态转移方程式： { g [ i + 1 ] [ j + 1 ] [ k + 1 ] + = P × g [ i ] [ j ] [ k ] g [ i − 1 ] [ 1 ] [ k + 1 ] + = ( 1 − P ) × g [ i ] [ j ] [ k ] \begin{cases}g[i+1][j+1][k+1]+=P\times g[i][j][k]\\g[i-1][1][k+1]+=(1-P)\times g[i][j][k]\end{cases} {g[i+1][j+1][k+1]+=P×g[i][j][k]g[i−1][1][k+1]+=(1−P)×g[i][j][k]​

答案即为所有的 g [ i ] [ j ] [ k ] × j g[i][j][k]\times j g[i][j][k]×j的和。

但这样做不太容易，我们换一种。定义状态 f [ a ] [ b ] [ c ] [ d ] [ i ] f[a][b][c][d][i] f[a][b][c][d][i]为当前走了 i i i关，有 a a a条命，连胜 b b b关，接下来经过若干步后走到状态 c , d c,d c,d。记最终状态为 e 1 , e 2 e_1,e_2 e1​,e2​。

不难发现 f [ a ] [ b ] [ c ] [ d ] [ i ] f[a][b][c][d][i] f[a][b][c][d][i]对最终状态 f [ a ] [ b ] [ e 1 ] [ e 2 ] [ N ] f[a][b][e_1][e_2][N] f[a][b][e1​][e2​][N]有贡献，该状态可转移至 f [ a ] [ b ] [ c + 1 ] [ d + 1 ] [ i + 1 ] f[a][b][c+1][d+1][i+1] f[a][b][c+1][d+1][i+1]和状态 f [ a ] [ b ] [ c − 1 ] [ 1 ] [ i + 1 ] f[a][b][c-1][1][i+1] f[a][b][c−1][1][i+1]。为了方便矩乘，我们将最终状态记为 f [ a ] [ b ] [ e 1 ] [ e 2 ] [ i + 1 ] f[a][b][e_1][e_2][i+1] f[a][b][e1​][e2​][i+1]，这是没有影响的。

由于 R , Q R,Q R,Q很小，我们可以对它所有可能出现的状态进行编号压进矩阵。那么这样就可以矩乘了。

由于矩阵里有很多位置是 0 0 0所以我们可以特判一下，让它们不能进去相乘即可。（其实就是卡常数）

这题卡精度，EPS要多试几次。

参考代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;const double EPS=1e-15;int N,Q,R,S;
int siz;struct Matrix {double a[105][105];Matrix operator * (const Matrix &rhs) const {Matrix ret;memset(ret.a,0,sizeof ret.a);for(int i=0;i<=siz;i++)for(int j=0;j<=siz;j++) {if(a[i][j]<EPS)continue;for(int k=0;k<=siz;k++) {if(rhs.a[j][k]<EPS)continue;ret.a[i][k]+=(a[i][j]*rhs.a[j][k]);}}return ret;}
};Matrix QuickPow(Matrix a,int k) {Matrix ret;memset(ret.a,0,sizeof ret.a);for(int i=0;i<=siz;i++)ret.a[i][i]=1;while(k) {if(k&1)ret=(ret*a);a=(a*a);k>>=1;}return ret;
}int num[25][25];
int cnt=0;void Prepare() {for(int i=1;i<=Q;i++)for(int j=1;j<=R;j++)num[i][j]=cnt++;
}bool check(double p) {Matrix s;memset(s.a,0,sizeof s.a);s.a[cnt][cnt]=1;for(int i=1;i<=Q;i++)for(int j=1;j<=R;j++) {s.a[num[i][j]][cnt]+=p*j;s.a[num[i][j]][num[min(i+1,Q)][min(j+1,R)]]+=p;if(i>1)s.a[num[i][j]][num[i-1][1]]+=(1-p);}s=QuickPow(s,N);return s.a[num[Q][1]][cnt]>S;
}int main() {#ifdef LOACLfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifscanf("%d %d %d %d",&N,&R,&Q,&S);double lb=0,ub=1;siz=Q*R;Prepare();if(check(1.0)==false) {puts("Impossible.");return 0;}while(lb+EPS<ub) {double mid=(lb+ub)/2;if(check(mid))ub=mid;else lb=mid;}printf("%.6f",lb);return 0;
}

C.【集训队互测 2012】Bomb

题目

题目描述

A 国和 B 国是两个超级大国，长期处于冷战状态；

A 国在 B 国中设有 N 个情报站，编号为 1,2,3, …… ,N ，每个情报站有一个坐标 (Xi,Yi) 。但是， A 国的工作人员发现，每个情报站里都被埋上了炸弹！

这些炸弹非常特殊 ， 只要同时拆除其中的三个炸弹 ， 所有炸弹就都不会爆炸了。

由于各个情报站联络需要代价 ， 拆除炸弹需要花费的总代价为这些炸弹两两之间的曼哈顿距离和。

现在 A 国的指挥部门找到了你 ， 希望知道可能需要的最大代价和最小代价 。

输入

输入的第一行包含一个整数 N 。接下来 N 行，第 i+1 行两个整数 Xi,Yi ，表示第 i 个情报站的坐标。

输出

输出两行 ， 每行包含一个整数 ， 第一行表示可能的最大代价 ， 第二行表示可能的最小代价。

样例输入

4
1 1
1 2
2 1
2 3

样例输出

6
4

数据范围

对于 30% 的数据， N<=500

对于另外 10% 的数据，每个点出现至少两遍

对于 50% 的数据， N<=1000

对于 60% 的数据， N<=8000

对于 70% 的数据， N<=15000

对于 80% 的数据， N<=50000

对于 100% 的数据， N<=100000 ， 0<=Xi,Yi<=10^8

【 注释 】

对于两个点 (X0,Y0),(X1,Y1) ，

它们之间的曼哈顿距离为 abs(X0-X1)+abs(Y0-Y1) 。

分析

这道题画一画图就可以发现三个点的曼哈顿距离构成了一个矩形，那么我们就可以将式子转化为： 2 ( X max ⁡ − X min ⁡ + Y max ⁡ − Y min ⁡ ) 2(X_{\max}-X_{\min}+Y_{\max}-Y_{\min}) 2(Xmax​−Xmin​+Ymax​−Ymin​)，分别求出最大最小值即可。

求解最大值可以贪心，不难发现这个值由 X max ⁡ , X min ⁡ , Y max ⁡ , Y min ⁡ , ( X + Y ) max ⁡ , ( X + Y ) min ⁡ , ( X − Y ) max ⁡ , ( X − Y ) min ⁡ X_{\max},X_{\min},Y_{\max},Y_{\min},(X+Y)_{\max},(X+Y)_{\min},(X-Y)_{\max},(X-Y)_{\min} Xmax​,Xmin​,Ymax​,Ymin​,(X+Y)max​,(X+Y)min​,(X−Y)max​,(X−Y)min​中的三个组成，共四种情况。

而求解最小值可以考虑模仿最近点对进行分治。

分治时只是多算了一个点，再用一个循环枚举即可。

为避免卡常，我在当前点数小于20的时候直接暴力。

这道题也可以用线段树做，简要提一下做法：

这种做法应用了式子转化为 2 ( X max ⁡ − X min ⁡ + Y max ⁡ − Y min ⁡ ) 2(X_{\max}-X_{\min}+Y_{\max}-Y_{\min}) 2(Xmax​−Xmin​+Ymax​−Ymin​)的结论。

设选中的三个点分别是 A , B , C A,B,C A,B,C且满足 x A ≤ x B ≤ x C x_A\le x_B\le x_C xA​≤xB​≤xC​。

我们需要讨论两种情况：

• 若只有 A , C A,C A,C确定了矩形的周长即 y A ≤ y B ≤ y C y_A\le y_B\le y_C yA​≤yB​≤yC​，这时答案为 2 ( x C + y C − x A − y A ) 2(x_C+y_C-x_A-y_A) 2(xC​+yC​−xA​−yA​)，此时对于每个点，我们用线段树存下它作为 B B B时的 x C + y C x_C+y_C xC​+yC​和 x A + y A x_A+y_A xA​+yA​最大最小值；
• 若三个点都有贡献即 y B ≤ y A y_B\le y_A yB​≤yA​，此时答案为 2 ( x C + y C − x A − y B ) 2(x_C+y_C-x_A-y_B) 2(xC​+yC​−xA​−yB​)，还是考虑枚举中间点 B B B，所以维护所有可能左边的 A A A和右边的 C C C的值，这个也用线段树搞。我们维护 A A A构成的集合，倒序计算答案，查询 B B B时先删掉 B B B，查完后插入 C C C集合，就是在线段树上区间修改。

由于在四个方向上都有可能存在答案，所以我们应当将坐标旋转后再取答案。

参考代码

分治

#include<cstdio>
#include<algorithm>
using namespace std;const int Maxn=100000;
const int INF=0x3f3f3f3f;struct Node {int x,y;
};
bool cmp1(Node lhs,Node rhs) {return lhs.x==rhs.x?lhs.y<rhs.y:lhs.x<rhs.x;}
bool cmp2(Node lhs,Node rhs) {return lhs.y==rhs.y?lhs.x<rhs.x:lhs.y<rhs.y;}int N;
Node A[Maxn+5],tmp[Maxn+5];
int ans_max,ans_min;int calc(Node i,Node j,Node k) {return 2*max(i.x,max(j.x,k.x))-2*min(i.x,min(j.x,k.x))+2*max(i.y,max(j.y,k.y))-2*min(i.y,min(j.y,k.y));
}
inline int Abs(int x) {if(x>=0)return x;else return -x;
}
void DFS(int l,int r) {if(r-l+1<20) {for(int i=l;i<=r;i++)for(int j=i+1;j<=r;j++)for(int k=j+1;k<=r;k++)ans_min=min(ans_min,calc(A[i],A[j],A[k]));return;}int mid=(l+r)>>1;DFS(l,mid),DFS(mid+1,r);int cnt=0;for(int i=mid+1;i<=r;i++)if(Abs(A[i].x-A[mid].x)<ans_min)tmp[++cnt]=A[i];else break;for(int i=mid;i>=l;i--)if(Abs(A[mid].x-A[i].x)<ans_min)tmp[++cnt]=A[i];else break;sort(tmp+1,tmp+cnt+1,cmp2);int l1=1;for(int i=3;i<=cnt;i++) {while(Abs(tmp[l1].y-tmp[i].y)>=ans_min)l1++;//y值过小的也应该排除for(int j=l1;j<i;j++)for(int k=j+1;k<i;k++)ans_min=min(ans_min,calc(tmp[i],tmp[j],tmp[k]));}
}int main() {#ifdef LOACLfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifscanf("%d",&N);ans_max=-INF,ans_min=INF;int Xmin=INF,Xmax=-INF,Ymin=INF,Ymax=-INF,T1min=INF,T1max=-INF,T2min=INF,T2max=-INF;for(int i=1;i<=N;i++) {scanf("%d %d",&A[i].x,&A[i].y);Xmin=min(Xmin,A[i].x),Xmax=max(Xmax,A[i].x),Ymin=min(Ymin,A[i].y),Ymax=max(Ymax,A[i].y);T1max=max(T1max,A[i].x+A[i].y),T1min=min(T1min,A[i].x+A[i].y);T2max=max(T2max,A[i].x-A[i].y),T2min=min(T2min,A[i].x-A[i].y);}ans_max=max(T1max-Xmin-Ymin,max(Xmax+Ymax-T1min,max(T2max+Ymax-Xmin,Xmax-Ymin-T2min)))*2;sort(A+1,A+N+1,cmp1);DFS(1,N);printf("%d\n%d\n",ans_max,ans_min);return 0;
}

线段树

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;const int Maxn=100000;
const int INF=0x3f3f3f3f;int N;
struct Point {int x,y;
};
bool cmp_x(Point lhs,Point rhs) {return lhs.x==rhs.x?lhs.y<rhs.y:lhs.x<rhs.x;}
bool cmp_y(Point lhs,Point rhs) {return lhs.y==rhs.y?lhs.x<rhs.x:lhs.y<rhs.y;}Point A[Maxn+5],tmp[Maxn+5];
int t1[Maxn+5];struct SegmentTree1 {struct Segment {int mx,mn;};Segment t[Maxn*4+5];void pushup(int rt) {t[rt].mx=max(t[rt<<1].mx,t[rt<<1|1].mx);t[rt].mn=min(t[rt<<1].mn,t[rt<<1|1].mn);}void build(int rt,int l,int r) {t[rt].mx=-INF,t[rt].mn=INF;if(l==r)return;int mid=(l+r)>>1;build(rt<<1,l,mid),build(rt<<1|1,mid+1,r);}void modify(int rt,int l,int r,int pos,int val) {if(l==r) {t[rt].mx=max(t[rt].mx,val);t[rt].mn=min(t[rt].mn,val);return;}int mid=(l+r)>>1;if(pos<=mid)modify(rt<<1,l,mid,pos,val);else modify(rt<<1|1,mid+1,r,pos,val);pushup(rt);}int query_max(int rt,int l,int r,int ql,int qr) {if(ql<=l&&r<=qr)return t[rt].mx;int mid=(l+r)>>1;int ret=-INF;if(ql<=mid)ret=max(ret,query_max(rt<<1,l,mid,ql,qr));if(qr>=mid+1)ret=max(ret,query_max(rt<<1|1,mid+1,r,ql,qr));return ret;}int query_min(int rt,int l,int r,int ql,int qr) {if(ql<=l&&r<=qr)return t[rt].mn;int mid=(l+r)>>1;int ret=INF;if(ql<=mid)ret=min(ret,query_min(rt<<1,l,mid,ql,qr));if(qr>=mid+1)ret=min(ret,query_min(rt<<1|1,mid+1,r,ql,qr));return ret;}
};
struct SegmentTree2 {struct Segment {int mx,mn;int mx_tmp,mn_tmp;int tag_mx,tag_mn;};Segment t[Maxn*4+5];void pushup(int rt) {t[rt].mx=max(t[rt<<1].mx,t[rt<<1|1].mx);t[rt].mx_tmp=max(t[rt<<1].mx_tmp,t[rt<<1|1].mx_tmp);t[rt].mn=min(t[rt<<1].mn,t[rt<<1|1].mn);t[rt].mn_tmp=min(t[rt<<1].mn_tmp,t[rt<<1|1].mn_tmp);}void pushdown(int rt) {t[rt<<1].mx=max(t[rt<<1].mx,t[rt<<1].mx_tmp+t[rt].tag_mx);t[rt<<1].tag_mx=max(t[rt<<1].tag_mx,t[rt].tag_mx);t[rt<<1].mn=min(t[rt<<1].mn,t[rt<<1].mn_tmp+t[rt].tag_mn);t[rt<<1].tag_mn=min(t[rt<<1].tag_mn,t[rt].tag_mn);t[rt<<1|1].mx=max(t[rt<<1|1].mx,t[rt<<1|1].mx_tmp+t[rt].tag_mx);t[rt<<1|1].tag_mx=max(t[rt<<1|1].tag_mx,t[rt].tag_mx);t[rt<<1|1].mn=min(t[rt<<1|1].mn,t[rt<<1|1].mn_tmp+t[rt].tag_mn);t[rt<<1|1].tag_mn=min(t[rt<<1|1].tag_mn,t[rt].tag_mn);t[rt].tag_mx=-INF,t[rt].tag_mn=INF;}void build(int rt,int l,int r) {t[rt].tag_mx=-INF,t[rt].tag_mn=INF;if(l==r) {t[rt].mx_tmp=t[rt].mn_tmp=t1[l];t[rt].mx=-INF,t[rt].mn=INF;return;}int mid=(l+r)>>1;build(rt<<1,l,mid),build(rt<<1|1,mid+1,r);pushup(rt);}void del(int rt,int l,int r,int pos) {if(l==r) {t[rt].mx=t[rt].mx_tmp=-INF;t[rt].mn=t[rt].mn_tmp=INF;return;}pushdown(rt);int mid=(l+r)>>1;if(pos<=mid)del(rt<<1,l,mid,pos);else del(rt<<1|1,mid+1,r,pos);pushup(rt);}void modify(int rt,int l,int r,int ml,int mr,int val) {if(ml<=l&&r<=mr) {t[rt].mx=max(t[rt].mx,t[rt].mx_tmp+val);t[rt].tag_mx=max(t[rt].tag_mx,val);t[rt].mn=min(t[rt].mn,t[rt].mn_tmp+val);t[rt].tag_mn=min(t[rt].tag_mn,val);return;}pushdown(rt);int mid=(l+r)>>1;if(ml<=mid)modify(rt<<1,l,mid,ml,mr,val);if(mr>=mid+1)modify(rt<<1|1,mid+1,r,ml,mr,val);pushup(rt);}int query_max(int rt,int l,int r,int ql,int qr) {if(ql<=l&&r<=qr)return t[rt].mx;pushdown(rt);int mid=(l+r)>>1;int ret=-INF;if(ql<=mid)ret=max(ret,query_max(rt<<1,l,mid,ql,qr));if(qr>=mid+1)ret=max(ret,query_max(rt<<1|1,mid+1,r,ql,qr));pushup(rt);return ret;}int query_min(int rt,int l,int r,int ql,int qr) {if(ql<=l&&r<=qr)return t[rt].mn;pushdown(rt);int mid=(l+r)>>1;int ret=INF;if(ql<=mid)ret=min(ret,query_min(rt<<1,l,mid,ql,qr));if(qr>=mid+1)ret=min(ret,query_min(rt<<1|1,mid+1,r,ql,qr));pushup(rt);return ret;}
};int ans_max,ans_min;
SegmentTree1 Tree1;
SegmentTree2 Tree2;
int rnk[Maxn+5],L[Maxn+5];int FindL(int val) {int lb=1,ub=N;int ret;while(lb<=ub) {int mid=(lb+ub)>>1;if(tmp[mid].x>=val) {ret=mid;ub=mid-1;} else lb=mid+1;}return ret;
}
int FindR(int val) {int lb=1,ub=N;int ret;while(lb<=ub) {int mid=(lb+ub)>>1;if(tmp[mid].x<=val) {ret=mid;lb=mid+1;} else ub=mid-1;}return ret;
}int fmx[Maxn+5],fmn[Maxn+5];void Solve() {sort(A+1,A+N+1,cmp_x);for(int i=1;i<=N;i++)tmp[i].x=A[i].y,tmp[i].y=i;sort(tmp+1,tmp+N+1,cmp_x);for(int i=1;i<=N;i++)L[i]=FindL(A[i].y),rnk[tmp[i].y]=i;for(int i=1;i<=N;i++)t1[rnk[i]]=-A[i].x;Tree1.build(1,1,N);for(int i=1;i<=N;i++) {fmx[i]=Tree1.query_max(1,1,N,1,L[i]);fmn[i]=Tree1.query_min(1,1,N,1,L[i]);Tree1.modify(1,1,N,L[i],-A[i].x-A[i].y);}Tree1.build(1,1,N);for(int i=N;i>=1;i--) {ans_max=max(ans_max,Tree1.query_max(1,1,N,L[i],N)+fmx[i]);ans_min=min(ans_min,Tree1.query_min(1,1,N,L[i],N)+fmn[i]);Tree1.modify(1,1,N,L[i],A[i].x+A[i].y);}Tree2.build(1,1,N);for(int i=N;i>=1;i--) {Tree2.del(1,1,N,rnk[i]);ans_max=max(ans_max,Tree2.query_max(1,1,N,L[i],N)-A[i].y);ans_min=min(ans_min,Tree2.query_min(1,1,N,L[i],N)-A[i].y);Tree2.modify(1,1,N,1,FindR(A[i].y),A[i].x+A[i].y);}
}int main() {#ifdef LOACLfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifscanf("%d",&N);for(int i=1;i<=N;i++)scanf("%d %d",&A[i].x,&A[i].y);ans_max=-INF,ans_min=INF;Solve();for(int i=1;i<=N;i++)A[i].x*=-1,A[i].y*=-1;Solve();for(int i=1;i<=N;i++)A[i].x*=-1;Solve();for(int i=1;i<=N;i++)A[i].x*=-1,A[i].y*=-1;Solve();printf("%d\n%d\n",ans_max*2,ans_min*2);return 0;
}

中山纪中集训游记Day2+8.2模拟赛题解

Part.I游记

纪中的OJ真的。。。今天下午又炸一次。。。

今天模拟赛竟然是考的集训队互测的题。。。做到自闭。。。

一开考看见第一题，给我的感觉是要写树套树。。。然而我不想写。。。

然后就去看了第二题，看上去要用矩阵乘法。什么期望题啊，我写不来。。。（我矩乘都要忘完了。。。

看了看第三题，目测可用线段树解决。先打一发暴力再说。

这时机房里的某位同学因为上网干一些hhh的事情，被老师发现了，然后，机房的网就断了。。。

我开始写60分的做法（ O ( N 2 log ⁡ 2 N ) O(N^2\log_2N) O(N2log2​N)）然而我写的可持久化线段树炸了。。。调了半天勉强过样例。我写了个数据生成器和暴力程序对拍，结果才一组就挂了。。。

然后我就自闭了。。。

下午听讲题，讲题人讲到第一题暴力可过，因为第一题的时限是10s。。。F**k还是怪自己不够仔细。。。

第二题真的是用矩乘。。。然而考场上的我去做第三题了。。。

第三题我听的时候猛然发现我推的做法和题解相差不大。。。但是题解普通线段树解决的我为什么偏要写可持久化。。。(逃

最后只有30分。。。

Prat.II题解

A.【集训队互测 2012】Attack

题目

题目描述

chnlich 非常喜欢玩三国志这款游戏,并喜欢用一些策略出奇制胜。现在,他要开始征服世界的旅途了。他的敌人有N 座城市和N 个太守, N个城市可以看作在二维平面上的N 个点。N 座城市的标号为0,1,2,…,N-1。第i 座城市的坐标为(Xi,Yi),镇守这座城市的太守的能力值为Zi。

chnlich 每次会选择一个边平行于坐标轴的矩形区域,并奇袭其中太守能力值第K小的城市(奇袭结束之后城市与太守依然存在)。

不过,他的敌人经常会偷偷交换两座城市的太守,防止弱点被chnlich 发现。

现在,chnlich 想要知道,每次奇袭时他的敌人的能力值。

输入

输入的第一行包含两个整数 N,M,N 表示城市与太守的个数,M 表示接下来发生了 M 个事件。

输入的第二行到第 N+1行,每行包含三个整数,第 i+2行的三个整数依次表示编号为 i 的城市的 Xi,Yi,Zi,含义如题所述。

输入的第 N+2行到第 N+M+1行,每行有两种可能形式:

第一种

QUERY x0 y0 x1 y1 k

表示 chnlich 询问一个相对顶点为(x0,y0),(x1,y1)的矩形中,第 k 小能力值太

守的能力值。

第二种

SWAP x y

表示 chnlich 的敌人交换了编号为 x 和 y 两座城市的太守。

输出

对于每一个 QUERY,输出一行。

若不存在第 k 小能力值的太守,输出"It doesn’t exist."(不包含引号)。

否则输出一个整数,表示矩形内能力值第 k 小太守的能力值。

样例输入

3 5
1 1 1
2 2 2
3 3 3
QUERY 1 1 3 3 3
SWAP 0 1
QUERY 2 2 4 4 1
SWAP 2 2
QUERY 2 2 3 3 3

样例输出

3
1
It doesn’t exist.

数据范围

对于100%的数据, N ≤ 60000 , M ≤ 10000 , 0 ≤ X i , Y i , Z i ≤ 1 0 9 , k ≤ 1 0 9 N\le60000,M\le10000,0\le Xi,Yi,Zi\le10^9,k\le10^9 N≤60000,M≤10000,0≤Xi,Yi,Zi≤109,k≤109,保证所有操作均合法。

分析

纪中OJ的机器跑得真快，暴力跑得比标程快。。。（这玩意只跑了3.7s！！！

正解说要用什么划分树之类的东西（反正我不会。。。

参考代码

#include<cstdio>
#include<algorithm>
using namespace std;const int Maxn=600000;int N;
struct Point {int x,y;int z;
};
Point A[Maxn+5];
bool cmp(int lhs,int rhs) {return A[lhs].z<A[rhs].z;
}
int rnk[Maxn+5],pos[Maxn+5];int main() {#ifdef LOACLfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifint Q;scanf("%d %d",&N,&Q);for(int i=1;i<=N;i++) {scanf("%d %d %d",&A[i].x,&A[i].y,&A[i].z);rnk[i]=i;}sort(rnk+1,rnk+N+1,cmp);for(int i=1;i<=N;i++)pos[rnk[i]]=i;while(Q--) {char s[10];scanf("%s",s);if(s[0]=='S') {int a,b;scanf("%d %d",&a,&b);a++,b++;swap(rnk[pos[a]],rnk[pos[b]]),swap(A[a].z,A[b].z),swap(pos[a],pos[b]);} else {int cnt=0,x1,y1,x2,y2,k;scanf("%d %d %d %d %d",&x1,&y1,&x2,&y2,&k);if(x1>x2)swap(x1,x2);if(y1>y2)swap(y1,y2);bool flag=false;for(int i=1;i<=N&&cnt<k;i++)if(x1<=A[rnk[i]].x&&A[rnk[i]].x<=x2&&y1<=A[rnk[i]].y&&A[rnk[i]].y<=y2) {cnt++;if(cnt==k) {flag=true;printf("%d\n",A[rnk[i]].z);break;}}if(flag==false)puts("It doesn't exist.");}}return 0;
}

B.【集训队互测 2012】Contra

题目

题目描述

偶然间,chnlich 发现了他小时候玩过的一个游戏“魂斗罗”,于是决定怀旧。但是这是一个奇怪的魂斗罗 MOD。

有 N 个关卡,初始有 Q 条命。

每通过一个关卡,会得到 u 分和1条命,生命上限为 Q。其中 u=min(最近一次连续通过的关数,R)。

若没有通过这个关卡,将会失去1条命,并进入下一个关卡。

当没有生命或没有未挑战过的关卡时,游戏结束,得到的分数为每关得到的分数的总和。

由于 chnlich 好久不玩这个游戏了,每条命通过每个关卡的概率均为p(0<=p<=1),原先 chnlich 的最高分纪录是 S。

现在 chnlich 想要知道,当 p 至少为多少时,chnlich 期望获得的总分数能够超过原先的最高分。

输入

输入共一行,分别表示整数 N,整数 R,整数 Q,原先的最高分整数 S。

输出

输出共一行,若不存在这样的 p,输出"Impossible."(不包含引号),否则输出 p(保留6位小数)。

样例输入

【样例输入一】
4 2 1 5
【样例输入二】
12 3 2 12

样例输出

【样例输出一】
0.880606
【样例输出二】
0.687201

【数据说明】

对于20%的数据,N<=15

对于50%的数据,N<=10000

对于100%的数据,N<=10^8,1<=R<=20,1<=Q<=5,保证 S 是一个可能出现的分数。

【补充说明】

例如,当 N=12,R=3,Q=2时

第一关:未通过 u=0 获得分数0 总分为0 剩余生命1

第二关:通过 获得分数1 总分为1 剩余生命2

第三关:通过 获得分数2 总分为3 剩余生命2

第四关:通过 获得分数3 总分为6 剩余生命2

第五关:通过 获得分数3 总分为9 剩余生命2

第六关:未通过 获得分数0 总分为9 剩余生命1

第七关:通过 获得分数1 总分为10 剩余生命2

第八关:未通过 获得分数0 总分为10 剩余生命1

第九关:未通过 获得分数0 总分为10 剩余生命0

游戏结束 总分为10

这是 chnlich 游戏的一种可能性

分析

显然我们需要二分答案。

我们二分出一个答案 P P P，那我们如何去检验这个答案。一个显而易见的方案是做一个DP。

不难发现当前能否继续走下去和得分只和命数和连胜的关卡数有关，所以，我们设计一个这样的DP状态：

我们设 f [ i ] [ j ] [ k ] , g [ i ] [ j ] [ k ] f[i][j][k],g[i][j][k] f[i][j][k],g[i][j][k]为当前剩余 i i i条命，已经连胜 j j j关，过了 k k k关的概率和得分，状态转移方程式非常好列，那么总的数学期望就是 ∑ i = 1 n f [ 0 ] [ 0 ] [ i ] × g [ 0 ] [ 0 ] [ i ] + ∑ i = 1 Q ∑ i = 1 R f [ i ] [ j ] [ N ] × g [ i ] [ j ] [ N ] \sum_{i=1}^{n}{f[0][0][i]\times g[0][0][i]}+\sum_{i=1}^{Q}{\sum_{i=1}^{R}{f[i][j][N]\times g[i][j][N]}} ∑i=1n​f[0][0][i]×g[0][0][i]+∑i=1Q​∑i=1R​f[i][j][N]×g[i][j][N]。

但这需要两个数组，而矩乘只能有一个。我们必须重新定义状态。

不难发现，边DP边算得分其实是不必要的，我们最后计算得分其实也是可以的，所以我们只需求概率即可。

设 g [ i ] [ j ] [ k ] g[i][j][k] g[i][j][k]为当前剩余 i i i条命，已经连胜 j j j关，过了 k k k关的概率。

列出 g g g的状态转移方程式： { g [ i + 1 ] [ j + 1 ] [ k + 1 ] + = P × g [ i ] [ j ] [ k ] g [ i − 1 ] [ 1 ] [ k + 1 ] + = ( 1 − P ) × g [ i ] [ j ] [ k ] \begin{cases}g[i+1][j+1][k+1]+=P\times g[i][j][k]\\g[i-1][1][k+1]+=(1-P)\times g[i][j][k]\end{cases} {g[i+1][j+1][k+1]+=P×g[i][j][k]g[i−1][1][k+1]+=(1−P)×g[i][j][k]​

答案即为所有的 g [ i ] [ j ] [ k ] × j g[i][j][k]\times j g[i][j][k]×j的和。

但这样做不太容易，我们换一种。定义状态 f [ a ] [ b ] [ c ] [ d ] [ i ] f[a][b][c][d][i] f[a][b][c][d][i]为当前走了 i i i关，有 a a a条命，连胜 b b b关，接下来经过若干步后走到状态 c , d c,d c,d。记最终状态为 e 1 , e 2 e_1,e_2 e1​,e2​。

不难发现 f [ a ] [ b ] [ c ] [ d ] [ i ] f[a][b][c][d][i] f[a][b][c][d][i]对最终状态 f [ a ] [ b ] [ e 1 ] [ e 2 ] [ N ] f[a][b][e_1][e_2][N] f[a][b][e1​][e2​][N]有贡献，该状态可转移至 f [ a ] [ b ] [ c + 1 ] [ d + 1 ] [ i + 1 ] f[a][b][c+1][d+1][i+1] f[a][b][c+1][d+1][i+1]和状态 f [ a ] [ b ] [ c − 1 ] [ 1 ] [ i + 1 ] f[a][b][c-1][1][i+1] f[a][b][c−1][1][i+1]。为了方便矩乘，我们将最终状态记为 f [ a ] [ b ] [ e 1 ] [ e 2 ] [ i + 1 ] f[a][b][e_1][e_2][i+1] f[a][b][e1​][e2​][i+1]，这是没有影响的。

由于 R , Q R,Q R,Q很小，我们可以对它所有可能出现的状态进行编号压进矩阵。那么这样就可以矩乘了。

由于矩阵里有很多位置是 0 0 0所以我们可以特判一下，让它们不能进去相乘即可。（其实就是卡常数）

这题卡精度，EPS要多试几次。

参考代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;const double EPS=1e-15;int N,Q,R,S;
int siz;struct Matrix {double a[105][105];Matrix operator * (const Matrix &rhs) const {Matrix ret;memset(ret.a,0,sizeof ret.a);for(int i=0;i<=siz;i++)for(int j=0;j<=siz;j++) {if(a[i][j]<EPS)continue;for(int k=0;k<=siz;k++) {if(rhs.a[j][k]<EPS)continue;ret.a[i][k]+=(a[i][j]*rhs.a[j][k]);}}return ret;}
};Matrix QuickPow(Matrix a,int k) {Matrix ret;memset(ret.a,0,sizeof ret.a);for(int i=0;i<=siz;i++)ret.a[i][i]=1;while(k) {if(k&1)ret=(ret*a);a=(a*a);k>>=1;}return ret;
}int num[25][25];
int cnt=0;void Prepare() {for(int i=1;i<=Q;i++)for(int j=1;j<=R;j++)num[i][j]=cnt++;
}bool check(double p) {Matrix s;memset(s.a,0,sizeof s.a);s.a[cnt][cnt]=1;for(int i=1;i<=Q;i++)for(int j=1;j<=R;j++) {s.a[num[i][j]][cnt]+=p*j;s.a[num[i][j]][num[min(i+1,Q)][min(j+1,R)]]+=p;if(i>1)s.a[num[i][j]][num[i-1][1]]+=(1-p);}s=QuickPow(s,N);return s.a[num[Q][1]][cnt]>S;
}int main() {#ifdef LOACLfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifscanf("%d %d %d %d",&N,&R,&Q,&S);double lb=0,ub=1;siz=Q*R;Prepare();if(check(1.0)==false) {puts("Impossible.");return 0;}while(lb+EPS<ub) {double mid=(lb+ub)/2;if(check(mid))ub=mid;else lb=mid;}printf("%.6f",lb);return 0;
}

C.【集训队互测 2012】Bomb

题目

题目描述

A 国和 B 国是两个超级大国，长期处于冷战状态；

A 国在 B 国中设有 N 个情报站，编号为 1,2,3, …… ,N ，每个情报站有一个坐标 (Xi,Yi) 。但是， A 国的工作人员发现，每个情报站里都被埋上了炸弹！

这些炸弹非常特殊 ， 只要同时拆除其中的三个炸弹 ， 所有炸弹就都不会爆炸了。

由于各个情报站联络需要代价 ， 拆除炸弹需要花费的总代价为这些炸弹两两之间的曼哈顿距离和。

现在 A 国的指挥部门找到了你 ， 希望知道可能需要的最大代价和最小代价 。

输入

输入的第一行包含一个整数 N 。接下来 N 行，第 i+1 行两个整数 Xi,Yi ，表示第 i 个情报站的坐标。

输出

输出两行 ， 每行包含一个整数 ， 第一行表示可能的最大代价 ， 第二行表示可能的最小代价。

样例输入

4
1 1
1 2
2 1
2 3

样例输出

6
4

数据范围

对于 30% 的数据， N<=500

对于另外 10% 的数据，每个点出现至少两遍

对于 50% 的数据， N<=1000

对于 60% 的数据， N<=8000

对于 70% 的数据， N<=15000

对于 80% 的数据， N<=50000

对于 100% 的数据， N<=100000 ， 0<=Xi,Yi<=10^8

【 注释 】

对于两个点 (X0,Y0),(X1,Y1) ，

它们之间的曼哈顿距离为 abs(X0-X1)+abs(Y0-Y1) 。

分析

这道题画一画图就可以发现三个点的曼哈顿距离构成了一个矩形，那么我们就可以将式子转化为： 2 ( X max ⁡ − X min ⁡ + Y max ⁡ − Y min ⁡ ) 2(X_{\max}-X_{\min}+Y_{\max}-Y_{\min}) 2(Xmax​−Xmin​+Ymax​−Ymin​)，分别求出最大最小值即可。

求解最大值可以贪心，不难发现这个值由 X max ⁡ , X min ⁡ , Y max ⁡ , Y min ⁡ , ( X + Y ) max ⁡ , ( X + Y ) min ⁡ , ( X − Y ) max ⁡ , ( X − Y ) min ⁡ X_{\max},X_{\min},Y_{\max},Y_{\min},(X+Y)_{\max},(X+Y)_{\min},(X-Y)_{\max},(X-Y)_{\min} Xmax​,Xmin​,Ymax​,Ymin​,(X+Y)max​,(X+Y)min​,(X−Y)max​,(X−Y)min​中的三个组成，共四种情况。

而求解最小值可以考虑模仿最近点对进行分治。

分治时只是多算了一个点，再用一个循环枚举即可。

为避免卡常，我在当前点数小于20的时候直接暴力。

这道题也可以用线段树做，简要提一下做法：

这种做法应用了式子转化为 2 ( X max ⁡ − X min ⁡ + Y max ⁡ − Y min ⁡ ) 2(X_{\max}-X_{\min}+Y_{\max}-Y_{\min}) 2(Xmax​−Xmin​+Ymax​−Ymin​)的结论。

设选中的三个点分别是 A , B , C A,B,C A,B,C且满足 x A ≤ x B ≤ x C x_A\le x_B\le x_C xA​≤xB​≤xC​。

我们需要讨论两种情况：

• 若只有 A , C A,C A,C确定了矩形的周长即 y A ≤ y B ≤ y C y_A\le y_B\le y_C yA​≤yB​≤yC​，这时答案为 2 ( x C + y C − x A − y A ) 2(x_C+y_C-x_A-y_A) 2(xC​+yC​−xA​−yA​)，此时对于每个点，我们用线段树存下它作为 B B B时的 x C + y C x_C+y_C xC​+yC​和 x A + y A x_A+y_A xA​+yA​最大最小值；
• 若三个点都有贡献即 y B ≤ y A y_B\le y_A yB​≤yA​，此时答案为 2 ( x C + y C − x A − y B ) 2(x_C+y_C-x_A-y_B) 2(xC​+yC​−xA​−yB​)，还是考虑枚举中间点 B B B，所以维护所有可能左边的 A A A和右边的 C C C的值，这个也用线段树搞。我们维护 A A A构成的集合，倒序计算答案，查询 B B B时先删掉 B B B，查完后插入 C C C集合，就是在线段树上区间修改。

由于在四个方向上都有可能存在答案，所以我们应当将坐标旋转后再取答案。

参考代码

分治

#include<cstdio>
#include<algorithm>
using namespace std;const int Maxn=100000;
const int INF=0x3f3f3f3f;struct Node {int x,y;
};
bool cmp1(Node lhs,Node rhs) {return lhs.x==rhs.x?lhs.y<rhs.y:lhs.x<rhs.x;}
bool cmp2(Node lhs,Node rhs) {return lhs.y==rhs.y?lhs.x<rhs.x:lhs.y<rhs.y;}int N;
Node A[Maxn+5],tmp[Maxn+5];
int ans_max,ans_min;int calc(Node i,Node j,Node k) {return 2*max(i.x,max(j.x,k.x))-2*min(i.x,min(j.x,k.x))+2*max(i.y,max(j.y,k.y))-2*min(i.y,min(j.y,k.y));
}
inline int Abs(int x) {if(x>=0)return x;else return -x;
}
void DFS(int l,int r) {if(r-l+1<20) {for(int i=l;i<=r;i++)for(int j=i+1;j<=r;j++)for(int k=j+1;k<=r;k++)ans_min=min(ans_min,calc(A[i],A[j],A[k]));return;}int mid=(l+r)>>1;DFS(l,mid),DFS(mid+1,r);int cnt=0;for(int i=mid+1;i<=r;i++)if(Abs(A[i].x-A[mid].x)<ans_min)tmp[++cnt]=A[i];else break;for(int i=mid;i>=l;i--)if(Abs(A[mid].x-A[i].x)<ans_min)tmp[++cnt]=A[i];else break;sort(tmp+1,tmp+cnt+1,cmp2);int l1=1;for(int i=3;i<=cnt;i++) {while(Abs(tmp[l1].y-tmp[i].y)>=ans_min)l1++;//y值过小的也应该排除for(int j=l1;j<i;j++)for(int k=j+1;k<i;k++)ans_min=min(ans_min,calc(tmp[i],tmp[j],tmp[k]));}
}int main() {#ifdef LOACLfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifscanf("%d",&N);ans_max=-INF,ans_min=INF;int Xmin=INF,Xmax=-INF,Ymin=INF,Ymax=-INF,T1min=INF,T1max=-INF,T2min=INF,T2max=-INF;for(int i=1;i<=N;i++) {scanf("%d %d",&A[i].x,&A[i].y);Xmin=min(Xmin,A[i].x),Xmax=max(Xmax,A[i].x),Ymin=min(Ymin,A[i].y),Ymax=max(Ymax,A[i].y);T1max=max(T1max,A[i].x+A[i].y),T1min=min(T1min,A[i].x+A[i].y);T2max=max(T2max,A[i].x-A[i].y),T2min=min(T2min,A[i].x-A[i].y);}ans_max=max(T1max-Xmin-Ymin,max(Xmax+Ymax-T1min,max(T2max+Ymax-Xmin,Xmax-Ymin-T2min)))*2;sort(A+1,A+N+1,cmp1);DFS(1,N);printf("%d\n%d\n",ans_max,ans_min);return 0;
}

线段树

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;const int Maxn=100000;
const int INF=0x3f3f3f3f;int N;
struct Point {int x,y;
};
bool cmp_x(Point lhs,Point rhs) {return lhs.x==rhs.x?lhs.y<rhs.y:lhs.x<rhs.x;}
bool cmp_y(Point lhs,Point rhs) {return lhs.y==rhs.y?lhs.x<rhs.x:lhs.y<rhs.y;}Point A[Maxn+5],tmp[Maxn+5];
int t1[Maxn+5];struct SegmentTree1 {struct Segment {int mx,mn;};Segment t[Maxn*4+5];void pushup(int rt) {t[rt].mx=max(t[rt<<1].mx,t[rt<<1|1].mx);t[rt].mn=min(t[rt<<1].mn,t[rt<<1|1].mn);}void build(int rt,int l,int r) {t[rt].mx=-INF,t[rt].mn=INF;if(l==r)return;int mid=(l+r)>>1;build(rt<<1,l,mid),build(rt<<1|1,mid+1,r);}void modify(int rt,int l,int r,int pos,int val) {if(l==r) {t[rt].mx=max(t[rt].mx,val);t[rt].mn=min(t[rt].mn,val);return;}int mid=(l+r)>>1;if(pos<=mid)modify(rt<<1,l,mid,pos,val);else modify(rt<<1|1,mid+1,r,pos,val);pushup(rt);}int query_max(int rt,int l,int r,int ql,int qr) {if(ql<=l&&r<=qr)return t[rt].mx;int mid=(l+r)>>1;int ret=-INF;if(ql<=mid)ret=max(ret,query_max(rt<<1,l,mid,ql,qr));if(qr>=mid+1)ret=max(ret,query_max(rt<<1|1,mid+1,r,ql,qr));return ret;}int query_min(int rt,int l,int r,int ql,int qr) {if(ql<=l&&r<=qr)return t[rt].mn;int mid=(l+r)>>1;int ret=INF;if(ql<=mid)ret=min(ret,query_min(rt<<1,l,mid,ql,qr));if(qr>=mid+1)ret=min(ret,query_min(rt<<1|1,mid+1,r,ql,qr));return ret;}
};
struct SegmentTree2 {struct Segment {int mx,mn;int mx_tmp,mn_tmp;int tag_mx,tag_mn;};Segment t[Maxn*4+5];void pushup(int rt) {t[rt].mx=max(t[rt<<1].mx,t[rt<<1|1].mx);t[rt].mx_tmp=max(t[rt<<1].mx_tmp,t[rt<<1|1].mx_tmp);t[rt].mn=min(t[rt<<1].mn,t[rt<<1|1].mn);t[rt].mn_tmp=min(t[rt<<1].mn_tmp,t[rt<<1|1].mn_tmp);}void pushdown(int rt) {t[rt<<1].mx=max(t[rt<<1].mx,t[rt<<1].mx_tmp+t[rt].tag_mx);t[rt<<1].tag_mx=max(t[rt<<1].tag_mx,t[rt].tag_mx);t[rt<<1].mn=min(t[rt<<1].mn,t[rt<<1].mn_tmp+t[rt].tag_mn);t[rt<<1].tag_mn=min(t[rt<<1].tag_mn,t[rt].tag_mn);t[rt<<1|1].mx=max(t[rt<<1|1].mx,t[rt<<1|1].mx_tmp+t[rt].tag_mx);t[rt<<1|1].tag_mx=max(t[rt<<1|1].tag_mx,t[rt].tag_mx);t[rt<<1|1].mn=min(t[rt<<1|1].mn,t[rt<<1|1].mn_tmp+t[rt].tag_mn);t[rt<<1|1].tag_mn=min(t[rt<<1|1].tag_mn,t[rt].tag_mn);t[rt].tag_mx=-INF,t[rt].tag_mn=INF;}void build(int rt,int l,int r) {t[rt].tag_mx=-INF,t[rt].tag_mn=INF;if(l==r) {t[rt].mx_tmp=t[rt].mn_tmp=t1[l];t[rt].mx=-INF,t[rt].mn=INF;return;}int mid=(l+r)>>1;build(rt<<1,l,mid),build(rt<<1|1,mid+1,r);pushup(rt);}void del(int rt,int l,int r,int pos) {if(l==r) {t[rt].mx=t[rt].mx_tmp=-INF;t[rt].mn=t[rt].mn_tmp=INF;return;}pushdown(rt);int mid=(l+r)>>1;if(pos<=mid)del(rt<<1,l,mid,pos);else del(rt<<1|1,mid+1,r,pos);pushup(rt);}void modify(int rt,int l,int r,int ml,int mr,int val) {if(ml<=l&&r<=mr) {t[rt].mx=max(t[rt].mx,t[rt].mx_tmp+val);t[rt].tag_mx=max(t[rt].tag_mx,val);t[rt].mn=min(t[rt].mn,t[rt].mn_tmp+val);t[rt].tag_mn=min(t[rt].tag_mn,val);return;}pushdown(rt);int mid=(l+r)>>1;if(ml<=mid)modify(rt<<1,l,mid,ml,mr,val);if(mr>=mid+1)modify(rt<<1|1,mid+1,r,ml,mr,val);pushup(rt);}int query_max(int rt,int l,int r,int ql,int qr) {if(ql<=l&&r<=qr)return t[rt].mx;pushdown(rt);int mid=(l+r)>>1;int ret=-INF;if(ql<=mid)ret=max(ret,query_max(rt<<1,l,mid,ql,qr));if(qr>=mid+1)ret=max(ret,query_max(rt<<1|1,mid+1,r,ql,qr));pushup(rt);return ret;}int query_min(int rt,int l,int r,int ql,int qr) {if(ql<=l&&r<=qr)return t[rt].mn;pushdown(rt);int mid=(l+r)>>1;int ret=INF;if(ql<=mid)ret=min(ret,query_min(rt<<1,l,mid,ql,qr));if(qr>=mid+1)ret=min(ret,query_min(rt<<1|1,mid+1,r,ql,qr));pushup(rt);return ret;}
};int ans_max,ans_min;
SegmentTree1 Tree1;
SegmentTree2 Tree2;
int rnk[Maxn+5],L[Maxn+5];int FindL(int val) {int lb=1,ub=N;int ret;while(lb<=ub) {int mid=(lb+ub)>>1;if(tmp[mid].x>=val) {ret=mid;ub=mid-1;} else lb=mid+1;}return ret;
}
int FindR(int val) {int lb=1,ub=N;int ret;while(lb<=ub) {int mid=(lb+ub)>>1;if(tmp[mid].x<=val) {ret=mid;lb=mid+1;} else ub=mid-1;}return ret;
}int fmx[Maxn+5],fmn[Maxn+5];void Solve() {sort(A+1,A+N+1,cmp_x);for(int i=1;i<=N;i++)tmp[i].x=A[i].y,tmp[i].y=i;sort(tmp+1,tmp+N+1,cmp_x);for(int i=1;i<=N;i++)L[i]=FindL(A[i].y),rnk[tmp[i].y]=i;for(int i=1;i<=N;i++)t1[rnk[i]]=-A[i].x;Tree1.build(1,1,N);for(int i=1;i<=N;i++) {fmx[i]=Tree1.query_max(1,1,N,1,L[i]);fmn[i]=Tree1.query_min(1,1,N,1,L[i]);Tree1.modify(1,1,N,L[i],-A[i].x-A[i].y);}Tree1.build(1,1,N);for(int i=N;i>=1;i--) {ans_max=max(ans_max,Tree1.query_max(1,1,N,L[i],N)+fmx[i]);ans_min=min(ans_min,Tree1.query_min(1,1,N,L[i],N)+fmn[i]);Tree1.modify(1,1,N,L[i],A[i].x+A[i].y);}Tree2.build(1,1,N);for(int i=N;i>=1;i--) {Tree2.del(1,1,N,rnk[i]);ans_max=max(ans_max,Tree2.query_max(1,1,N,L[i],N)-A[i].y);ans_min=min(ans_min,Tree2.query_min(1,1,N,L[i],N)-A[i].y);Tree2.modify(1,1,N,1,FindR(A[i].y),A[i].x+A[i].y);}
}int main() {#ifdef LOACLfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifscanf("%d",&N);for(int i=1;i<=N;i++)scanf("%d %d",&A[i].x,&A[i].y);ans_max=-INF,ans_min=INF;Solve();for(int i=1;i<=N;i++)A[i].x*=-1,A[i].y*=-1;Solve();for(int i=1;i<=N;i++)A[i].x*=-1;Solve();for(int i=1;i<=N;i++)A[i].x*=-1,A[i].y*=-1;Solve();printf("%d\n%d\n",ans_max*2,ans_min*2);return 0;
}

本文标签： 中山纪中集训游记Day282模拟赛题解