首页 > 其他分享 >洛谷P8539 「Wdoi-2」来自地上的支援 题解

洛谷P8539 「Wdoi-2」来自地上的支援 题解

时间：2022-10-29 22:55:05浏览次数：69  
标签：P8539 洛谷 int 题解 st st2 max 65536 else

ST 表做法

思路

  • 当进行第 \(x\) 次操作时，若 \(b_1\) 到 \(b_{x-1}\) 中有比 \(b_x\) 大的数，那这次操作轮不到 \(b_x\)，并且前面的本来就比它大的数只会越来越大，所以以后的操作也永远轮不到 \(b_x\)。

    所以，\(b_x\) 一定要不小于 \(\underset{1\le i<x}{\max}\{b_i\}\)。

    问题来了：可以等于吗？

    不妨设前面最大的数为 \(b_j\)，并且 \(b_x=b_j\)。

    显然：\(b_j\)被操作过，也就是说，\(b_j>a_j\)。又因为\(b_x=a_x\)，所以：\(a_x>a_j\)。

    所以，根据规则 \(2\)，当 \(b_x=b_j\ (1\le j<x)\) 时，会选择 \(b_x\) 来处理，可以等于。

    这一部分的处理非常简单，不做赘述。

  • 接着考虑后面的数：若至少需操作 \(k\) 次，那么显然一定要满足 \(b_x>b_i\ (x<i<x+k)\)，也就是 \(a_x+v\ (i-x)>a_i\)（这里不能等于，想法和上面类似，此处省略说明过程）。

    将这个不等式移项，得 \(a_x>a_i-v\ (i-x)\)。

    因此，我们只需找出 \(\underset{x<i<x+k}{\max}\{a_i-v\ (i-x)\}\) 即可。

    我们设 \(x<i<j<x+k\)，通过减法来比较他们的大小：

    \[(\ a_i-v\ (i-x)\ )-(\ a_j-v\ (j-x)\ ) =a_i-a_j-v\ (j-i) \]

    会发现，\(x\) 被消掉了，也就是说，当两数未被操作时，它们加权后的大小比较与前面的数无关。

    那么，我们可以很自然地想到将 \(x_i\) 排序，使得我们不需考虑对于 \(b_{x+1}\) 到 \(b_n\) 的修改，然后用 ST 表 \(O\ (1)\) 地求出 \(\underset{x<i<x+k}{\max}\{a_i-v\ (i-x)\}\) 对应值的下标即可（ST 表存的是下标）。

    注意：在预处理 ST 表时，若 \(a_i=a_j\ (1\le i<j\le n)\)，则根据规则 \(3\) ，选择下标小的 \(i\)。

最终，答案为 \(\max\ \{\ \underset{1\le i<x}{\max}\{b_i\},\underset{x<i<x+k}{\max}\{a_i-v\ (i-x)\}+1\ \}\)。

ST 表预处理的时间复杂度为 \(O\ (n \log n)\)，查询的时间复杂度为 \(O\ (m)\) ，总时间复杂度为 \(O\ (n \log n)\) ，空间复杂度为 \(O\ (n \log n)\)。

代码

#include<bits/stdc++.h>
#define LL long long
using namespace std;
int read() {
	int s=0,f=1; char ch=getchar();
	while (ch<48 || ch>57) {if (ch=='-') f=-1; ch=getchar();}
	while (ch>=48 && ch<=57) {s=(s<<3)+(s<<1)+ch-48; ch=getchar();}
	return s*f;
}
const int N=2e6+5;
pair <int,int> q[N];
int n,m,v,a[N],b[N],w=1,max_num,st[N][20];
LL ans,ans1,ans2;
void ST_prework() {
	for (int i=1;i<=n;++i)
	st[i][0]=i;
	int t=log2(n);
	for (int k=1;k<=t;++k) {
		int len=(1<<k);
		for (int i=1;i+len-1<=n;++i) {
			if (a[st[i][k-1]]+(st[i+(len>>1)][k-1]-st[i][k-1])*v>a[st[i+(len>>1)][k-1]])
			st[i][k]=st[i][k-1];
			else st[i][k]=st[i+(len>>1)][k-1];
		}
	}
}
int query(int l,int r) {
	int k=log2(r-l+1),len=(1<<k);
	if (a[st[l][k]]+(st[r-len+1][k]-st[l][k])*v>a[st[r-len+1][k]])
	return st[l][k];
	return st[r-len+1][k];
}
int main() {
	n=read(),m=read(),v=read();
	for (int i=1;i<=n;++i)
	a[i]=read(),b[i]=a[i];
	for (int i=1;i<=m;++i)
	q[i].first=read(),q[i].second=read();
	sort(q+1,q+m+1);
	ST_prework();
	b[0]=1;
	for (int i=1;i<=n;++i) {
		while (q[w].first==i) {
			if (i+q[w].second-1>n) ans=0;
			else if (q[w].second==1) ans=b[max_num];
			else {
				int x=query(i+1,i+q[w].second-1);
				ans=max(b[max_num],a[x]-(x-i)*v+1);
			}
			ans1^=ans,ans2+=ans;
			++w;
		}
		if (b[i]>b[max_num] || b[i]==b[max_num] && a[i]>a[max_num])
		max_num=i;
		b[max_num]+=v;
	}
	printf("%lld %lld\n",ans1,ans2);
	return 0;
}

你以为这就结束了？

把这个代码交上去，你将获得 \(65\) 分，最后一个 Subtask 全部 MLE。

ST 表的空间复杂度为 \(O\ (n \log n)\) ，在空间只有 \(128\text{MB}\) 的情况下过不了 \(2\times10^6\)，用 \(\verb!sizeof!\) 算出的数组总空间为 \(183.106\text{MB}\)。

屑出题人为什么只给这么点空间（恼）

空间优化

\(\text{Update}\)：我写完题解才发现 \(st\) 数组的空间很多都没有利用完全，比如 \(st_{n/2,t}\) 到 \(st_{n,t}\ (t=\log_2n)\) 是没有用的，完全可以删去。 下文的前两种优化很麻烦（虽然我感觉这种也不方便），不过第三种优化还是挺有用的。

  • 很明显，占空间最多的是 \(st\) 数组，因为该数组存的是数组的下标，不超过 \(2\times10^6\)，所以可以把这个 \(\verb!int!\) 数组改成一个 \(\verb!unsigned char!\) 数组 \(st1\) 和一个 \(\verb!unsigned short!\) 数组 \(st2\)，对应的 \(st\) 值即为 \(st1\times65536+st2\)。

    注：下文提到的变量类型皆为 \(\verb!unsigned!\)。

    数组总空间为 \(144.959\text{MB}\)。

  • 还是不够，怎么办？

    用 \(\verb!bitset!\) 或者 \(\verb!bool!\)？然而，经 \(\verb!sizeof!\) 的测定，用 \(\verb!bitset!\) 无法优化空间；而在 C++ 中，\(\verb!bool!\) 的大小和 \(\verb!char!\) 一样。

    因为 \(2\times10^6<2^{21}\)，一个 \(\verb!short!\) 有 \(16\) 个数位，而一个 \(\verb!char!\) 有 \(8\) 个数位，\(\verb!char!\) 存的数只需 \(5\) 个数位来存，所以可以把上面的方法再次优化，让 \(5\) 个 \(\verb!char!\) 中存 \(8\) 个数的信息。

    数组总空间为 \(130.654\text{MB}\)。

  • ST表的空间已经被压到极限了，还是差一点，怎么办？

    \(\text{Update}\)：实际上没有被压到极限。

    考虑删减其他无用数组。

    仔细思考，会发现：\(b\) 数组其实无用，可以直接在 \(a\) 数组里修改，只需开一个变量记录被修改的数的初始值即可。

    数组总空间为 \(123.024\text{MB}\)。

看起来就很折磨的 AC 代码

#include<bits/stdc++.h>
#define LL long long
using namespace std;
int read() {
	int s=0,f=1; char ch=getchar();
	while (ch<48 || ch>57) {if (ch=='-') f=-1; ch=getchar();}
	while (ch>=48 && ch<=57) {s=(s<<3)+(s<<1)+(ch^48); ch=getchar();}
	return s*f;
}
const int N=2e6+5;
pair <int,int> q[N];
unsigned short st1[N][20];
unsigned char st2[1250005][20];
int n,m,v,a[N],w=1,max_num,init;
LL ans,ans1,ans2;
int st(int x,int y) {
	int res=st1[x][y];
	if (x%8==1) res+=int(st2[((x-1>>3)+1)*5-4][y]%32)*65536;
	else if (x%8==2) res+=int(st2[((x-1>>3)+1)*5-4][y]/32+(st2[((x-1>>3)+1)*5-3][y]%4)*8)*65536;
	else if (x%8==3) res+=int(st2[((x-1>>3)+1)*5-3][y]/4%32)*65536;
	else if (x%8==4) res+=int(st2[((x-1>>3)+1)*5-3][y]/128+(st2[((x-1>>3)+1)*5-2][y]%16)*2)*65536;
	else if (x%8==5) res+=int(st2[((x-1>>3)+1)*5-2][y]/16+(st2[((x-1>>3)+1)*5-1][y]%2)*16)*65536;
	else if (x%8==6) res+=int(st2[((x-1>>3)+1)*5-1][y]/2%32)*65536;
	else if (x%8==7) res+=int(st2[((x-1>>3)+1)*5-1][y]/64+(st2[((x-1>>3)+1)*5][y]%8)*4)*65536;
	else res+=int(st2[((x-1>>3)+1)*5][y]/8)*65536;
	return res;
}
void st_update(int x,int y,int z) {
	st1[x][y]=z%65536;
	if (x%8==1) st2[((x-1>>3)+1)*5-4][y]=st2[((x-1>>3)+1)*5-4][y]/32*32+z/65536;
	else if (x%8==2) {
		st2[((x-1>>3)+1)*5-4][y]=st2[((x-1>>3)+1)*5-4][y]%32+(z/65536%8)*32;
		st2[((x-1>>3)+1)*5-3][y]=st2[((x-1>>3)+1)*5-3][y]/4*4+z/65536/8;
	}
	else if (x%8==3) st2[((x-1>>3)+1)*5-3][y]=st2[((x-1>>3)+1)*5-3][y]%4+st2[((x-1>>3)+1)*5-3][y]/128*128+z/65536*4;
	else if (x%8==4) {
		st2[((x-1>>3)+1)*5-3][y]=st2[((x-1>>3)+1)*5-3][y]%128+(z/65536%2)*128;
		st2[((x-1>>3)+1)*5-2][y]=st2[((x-1>>3)+1)*5-2][y]/16*16+z/65536/2;
	}
	else if (x%8==5) {
		st2[((x-1>>3)+1)*5-2][y]=st2[((x-1>>3)+1)*5-2][y]%16+(z/65536%16)*16;
		st2[((x-1>>3)+1)*5-1][y]=st2[((x-1>>3)+1)*5-1][y]/2*2+z/65536/16;
	}
	else if (x%8==6) st2[((x-1>>3)+1)*5-1][y]=st2[((x-1>>3)+1)*5-1][y]%2+st2[((x-1>>3)+1)*5-1][y]/64*64+z/65536*2;
	else if (x%8==7) {
		st2[((x-1>>3)+1)*5-1][y]=st2[((x-1>>3)+1)*5-1][y]%64+(z/65536%4)*64;
		st2[((x-1>>3)+1)*5][y]=st2[((x-1>>3)+1)*5][y]/8*8+z/65536/4;
	}
	else st2[((x-1>>3)+1)*5][y]=st2[((x-1>>3)+1)*5][y]%8+z/65536*8;
}
void ST_prework() {
	for (int i=1;i<=n;++i)
	st_update(i,0,i);
	int t=log2(n);
	for (int k=1;k<=t;++k) {
		int len=(1<<k);
		for (int i=1;i+len-1<=n;++i) {
			if (a[st(i,k-1)]+(st(i+(len>>1),k-1)-st(i,k-1))*v>a[st(i+(len>>1),k-1)])
			st_update(i,k,st(i,k-1));
			else st_update(i,k,st(i+(len>>1),k-1));
		}
	}
}
int query(int l,int r) {
	int k=log2(r-l+1),len=(1<<k);
	if (a[st(l,k)]+(st(r-len+1,k)-st(l,k))*v>a[st(r-len+1,k)])
	return st(l,k);
	return st(r-len+1,k);
}
int main() {
	n=read(),m=read(),v=read();
	for (int i=1;i<=n;++i) a[i]=read();
	for (int i=1;i<=m;++i)
	q[i].first=read(),q[i].second=read();
	sort(q+1,q+m+1);
	ST_prework();
	a[0]=1;
	for (int i=1;i<=n;++i) {
		while (q[w].first==i) {
			if (i+q[w].second-1>n) ans=0;
			else if (q[w].second==1) ans=a[max_num];
			else {
				int x=query(i+1,i+q[w].second-1);
				ans=max(a[max_num],a[x]-(x-i)*v+1);
			}
			ans1^=ans,ans2+=ans;
			++w;
		}
		if (a[i]>a[max_num] || a[i]==a[max_num] && a[i]>init)
		max_num=i,init=a[i];
		a[max_num]+=v;
	}
	printf("%lld %lld\n",ans1,ans2);
	return 0;
}

\(1.36\text s\ /\ 123.66\text{MB}\)

写在题解后

这题我 \(20\) 分钟就写完了 \(65\) 分代码，结果调了半天才 AC。

洛谷出题人我求你别卡空间了！！！

我尝试过用 \(3\) 个 \(\verb!char!\) 数组存 \(4\) 个数的信息，再把 \(b\) 数组删掉，用 \(\verb!sizeof!\) 算出的数组总空间为 \(127.793\text{MB}\)，理论上能过，但是交上去还是 MLE；我的 AC 代码的数组总空间为 \(123.024\text{MB}\)，但洛谷上显示最多用了 \(123.66\text{MB}\)，所以不要把空间卡得太极限，实战中很容易 FST。

不过 NOIP 系列的题大多都是直接给 \(512\text{MB}\) ，很少会卡空间 .

如果我老老实实用线段树写可能还不用花这么久

标签：P8539,洛谷,int,题解,st,st2,max,65536,else
From： https://www.cnblogs.com/2Bpencil/p/16840126.html

相关文章

  • LeetCode 题解 | 1. 两数之和 Javascript 版
    题目给定一个整数数组nums 和一个整数目标值target，请你在该数组中找出和为目标值target 的那 两个 整数，并返回它们的数组下标。你可以假设每种输入只会对应一个......
  • LeetCode 题解 ｜ 3. 无重复字符的最长子串 Javascript
    /***@param{string}str*@returnsnumber*思路：1.start与range组合成一个窗口，窗口内的子串就是当前最长不重复的字符串*2.range每次循环递增*......
  • LeetCode 题解｜6. Z 字形变换
    /***@param{string}s*@param{number}numRows*@return{string}*/varconvert=function(s,numRows){//存储结果constrows=[];//指针下一......
  • LeetCode 题解｜9. 回文数
    /***@param{number}x*@return{boolean}*/varisPalindrome=function(x){if(x<0){returnfalse;}letnum=x;letreverse=0;wh......
  • LeetCode 题解｜7. 整数反转
    /***@param{number}x*@return{number}*/varreverse=function(x){letres=0;while(x!=0){res=res*10+(x%10);//划重点......
  • CSP-S2022游记&几句话题解
    T1对于每一个点\(u\)，计算点权最大的三个点，满足\(dis(u,v)\lek+1,dis(1,v)\lek+1\)。然后枚举\(B,C\),\(3^2\)枚举即可。复杂度\(O(n^2)\)。考场代码#inclu......
  • python(牛客)试题解析1 - 入门级
    导航：一、NC103反转字符串二、NC141判断是否为回文字符串三、NC151最大公约数四、NC65斐波那契数列----------分-割-线-----------一、NC10......
  • P1597洛谷刷题
    #include<iostream>#include<string>usingnamespacestd;intmain(intargc,char**argv){ stringstr="a:=3;b:=4;c:=5"; for(inti=1;i<=3;i++){ ints......
  • 洛P8109题解
    摘自本人洛谷博客，原文章地址：https://www.luogu.com.cn/blog/cjtb666anran/solution-p8109本题原题目摘录：本场比赛共有\(n\)道题，Cirno已经精确预测了每道题目的AC队......
  • 期中问题解决
    要哭了，刚刚写完总结去查找错误，不到五分钟就找到了，能把分儿给我加上嘛1、保证数据库主键的唯一性------实现两个不同页面的跳转在添加语句里面加入ignore关键字，然后将函数......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99