每日卡常小技巧
Just_int_mian · · 个人记录
密码是图片链接。
前言
常数，真的是一个非常可怕的东西。它看似微小至极，在众多的复杂度分析中被一句
拥有小常数是一件非常值得夸耀的事情，你可以 1e9 过 1s，可以随便爆踩 std，甚至可以高高在上地看着同机房的同学们深深陷入卡常的痛苦深渊中。
相反，拥有大常数则非常的骇人听闻。
在当今这个大家都很强的 OI 界中，不是卡常，就是被卡常，谁会错过如此的大好机会？如果在比赛时因为常数挂了分，如果打 CF 时因为常数喜提 -50，如果打 AT 时因为常数吃了一发罚时，影响是不可估量的。
而这个时候，拥有小常数，即卡常的优势就显现出来了。养成了良好的卡常习惯，你也可以从一名大常数 OIer 变成一名和我完全相反的小常数 OIer，而这篇每日卡常小技巧就是为此所做。
正文
- 写数据结构如 Trie 等时尽量不要封装。
- 能不用可持久化尽量不用可持久化，其常数比普通线段树大得多。
- 数据结构少 Query。(from @nb_jzy)
- 写函数名、变量名少用大写字母...? (from @nb_jzy)
- 实测：
fread真的比getchar快得多。 - 2-SAT 开点建边能少则少，能用并查集就用并查集。(from @nb_jzy)
- 《天气之子》的女主是阳莱。(from @jr_zch)
- @nb_jzy 从主席树 6 个 Query 到 4 个再到 2 个最后 AC 的励志故事。
- 实测：非递归函数加
inline优化真的很大，可以将单点用时降低10 - 200 ms 不等，取决于数据点大小。尤其是重载运算符这种需要被调用多次的函数。 - 怎么感觉不吃晚饭会让常数变大呢？以后不能不吃晚饭了。
- 复杂度较大的函数尽量少运行，尝试多压缩操作，或使用别的操作代替。
实战小练习
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,k,q,a[1200005],dp[2][1200005],Q[1200005],cnt[2],Ans[1200005],d[1200005],Temp[2],vis[2][1200005];
struct node{
int l,r,id;
}A[600005],Q1[600005],Q2[600005];
struct Point{
int x,y;
}P[600005];
inline void BFS(int xa,int ya,int xb,int yb,int x,int y,int id){
if(id==0){
int Max=min(n,yb*k+xb),now=y*k+x;
dp[0][now]=0;
Temp[0]++;
vis[0][now]=Temp[0];
for(int i=now+1;i<=Max;++i){
dp[0][i]=-9999999999999999ll;
vis[0][i]=Temp[0];
if(i-k>=now){
dp[0][i]=max(dp[0][i],dp[0][i-k]+Q[i]-Q[i-k]);
}
dp[0][i]=max(dp[0][i],dp[0][i-1]);
}
}
else{
int Min=ya*k+xa,now=y*k+x;
dp[1][now]=0;
Temp[1]++;
vis[1][now]=Temp[1];
for(int i=now-1;i>=Min;--i){
dp[1][i]=-9999999999999999ll;
vis[1][i]=Temp[1];
if(i+k<=now){
dp[1][i]=max(dp[1][i],dp[1][i+k]+Q[i+k]-Q[i]);
}
dp[1][i]=max(dp[1][i],dp[1][i+1]);
}
}
return;
}
inline bool Check(Point A,Point a,Point b){
if(a.x<=A.x&&A.x<=b.x&&a.y<=A.y&&A.y<=b.y){
return true;
}
return false;
}
void Solve(int xa,int ya,int xb,int yb,int L,int R,bool Flag){//(x,y)->(ID:yk+x)
int Lenx=xb-xa+1,Leny=yb-ya+1,Mid;
if((xa>xb)||(ya>yb)||(xa==xb&&ya==yb)||L>R){
return;
}
if(Lenx<Leny){
Mid=(ya+yb)>>1;
for(int i=xa;i<=xb;++i){
int x=i,y=Mid,ID=y*k+x;
if(ID>n){
break;
}
BFS(xa,ya,xb,yb,x,y,0);//原图
BFS(xa,ya,xb,yb,x,y,1);//反图
for(int j=L;j<=R;++j){
if((!Check(P[A[j].l],Point{xa,ya},Point{xb,yb}))||(!Check(P[A[j].r],Point{xa,ya},Point{xb,yb}))){
continue;
}
if((vis[1][A[j].l]!=Temp[1])||(vis[0][A[j].r]!=Temp[0])){
continue;
}
Ans[A[j].id]=max(Ans[A[j].id],dp[1][A[j].l]+dp[0][A[j].r]);
}
}
int cnt1=0,cnt2=0;
for(int j=L;j<=R;++j){
if(P[A[j].l].y<=Mid&&P[A[j].r].y<=Mid){
++cnt1;
Q1[cnt1]=A[j];
}
else if(P[A[j].l].y>Mid&&P[A[j].r].y>Mid){
++cnt2;
Q2[cnt2]=A[j];
}
}
for(int i=L;i<=L+cnt1-1;++i){
A[i]=Q1[i-L+1];
}
for(int i=R-cnt2+1;i<=R;++i){
A[i]=Q2[i-R+cnt2];
}
Solve(xa,ya,xb,Mid,L,L+cnt1-1,Flag);
Solve(xa,Mid+1,xb,yb,R-cnt2+1,R,Flag);
}
else{
if(!Flag){
for(int i=ya;i<yb;++i){
BFS(xa,ya,xb,yb,0,i+1,0);
BFS(xa,ya,xb,yb,k-1,i,1);
for(int j=L;j<=R;j++){
if((!Check(P[A[j].l],Point{xa,ya},Point{xb,yb}))||(!Check(P[A[j].r],Point{xa,ya},Point{xb,yb}))){
continue;
}
if((vis[1][A[j].l]!=Temp[1])||(vis[0][A[j].r]!=Temp[0])){
continue;
}
Ans[A[j].id]=max(Ans[A[j].id],dp[1][A[j].l]+dp[0][A[j].r]);
}
}
}
Flag=true;
Mid=(xa+xb)>>1;
for(int i=ya;i<=yb;++i){
int x=Mid,y=i,ID=y*k+x;
if(ID>n){
break;
}
BFS(xa,ya,xb,yb,x,y,0);
BFS(xa,ya,xb,yb,x,y,1);
for(int j=L;j<=R;++j){
if((!Check(P[A[j].l],Point{xa,ya},Point{xb,yb}))||(!Check(P[A[j].r],Point{xa,ya},Point{xb,yb}))){
continue;
}
if((vis[1][A[j].l]!=Temp[1])||(vis[0][A[j].r]!=Temp[0])){
continue;
}
Ans[A[j].id]=max(Ans[A[j].id],dp[1][A[j].l]+dp[0][A[j].r]);
}
}
int cnt1=0,cnt2=0;
for(int j=L;j<=R;++j){
if(P[A[j].l].x<=Mid&&P[A[j].r].x<=Mid){
++cnt1;
Q1[cnt1]=A[j];
}
else if(P[A[j].l].x>Mid&&P[A[j].r].x>Mid){
++cnt2;
Q2[cnt2]=A[j];
}
}
for(int i=L;i<=L+cnt1-1;++i){
A[i]=Q1[i-L+1];
}
for(int i=R-cnt2+1;i<=R;++i){
A[i]=Q2[i-R+cnt2];
}
Solve(xa,ya,Mid,yb,L,L+cnt1-1,Flag);
Solve(Mid+1,ya,xb,yb,R-cnt2+1,R,Flag);
}
return;
}
namespace IO
{
#define SIZE (1<<24)
char in[SIZE],out[SIZE],*p1=in,*p2=in,*p3=out;
#define getchar() (p1==p2&&(p2=(p1=in)+fread(in,1,SIZE,stdin),p1==p2)?EOF:*p1++)
#define flush() (fwrite(p3=out,1,SIZE,stdout))
#define putchar(ch) (p3==out+SIZE&&flush(),*p3++=(ch))
template<typename type>
inline void read(type &x)
{
x=0;bool flag(0);char ch=getchar();
while(!isdigit(ch)) flag^=ch=='-',ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
flag?x=-x:0;
}
template<typename type>
inline void write(type x,bool flag=1)
{
x<0?x=-x,putchar('-'):0;static short Stack[50],top(0);
do Stack[++top]=x%10,x/=10;while(x);
while(top) putchar(Stack[top--]|48);
flag?putchar('\n'):putchar(' ');
}
#undef SIZE
#undef getchar
#undef putchar
#undef flush
}using namespace IO;
int main(){
// freopen("t.in","r",stdin);
// freopen("a.out","w",stdout);
read(n);
read(k);
read(q);
for(int i=1;i<=n;++i){
read(a[i]);
P[i].x=i%k;
P[i].y=i/k;
Q[i]=Q[i-1]+a[i];
}
for(int i=1;i<=q;++i){
read(A[i].l);
read(A[i].r);
--A[i].l;
A[i].id=i;
}
Solve(0,0,k-1,n/k,1,q,false);
for(int i=1;i<=q;++i){
write(Ans[i],1);
}
fwrite(out,1,p3-out,stdout);
return 0;
}这是 Just_int_mian 在 P9040 [PA2021] Desant 2 一题的次优解？？？代码。不是，怎么就变成次优解了？被学长给卡得比我还快了。
不管了，你的任务是将这份代码卡到 500 ms 以下，然后发给 Just_int_mian 以领取神秘奖励一份。
神秘奖励：帮你造数据。
实战小练习 1 已经有人快要完成了。太强了。