写这个题解的原因是发现自己写了很多sb错误导致分数 $300 \to 100$ 加上发现出题人输出$10^6$个数还不提供快速输出板子加上板子就能 $3s \to 1s$ 的神奇比赛体验就来写一下这个题解。（题目还是很水的。。）
A
一棵树，点有点权，$1$ 号点为根。点 $i$ 的答案是从根到 $i$ 路径上点的权值组成的序列有多少个后缀最大值（维护一个单调不增的单调栈的大小），求每个点的答案。$n \leq 10^6$
首先链情况就是单调栈。
首先因为单调栈的复杂度是均摊的所以我们不能回溯，我们可以考虑对于点 $i$ 找到它的祖先中距离它最近的 $a_v \geq a_i$，答案就是 $ans_i = ans_v+1$。
我当时做这个东西直接用了倍增，然后 MLE 了。
想一想还有另一种做法：单调栈复杂度不对是因为一个点会改多个元素，我们不妨只让他改一个元素：我们很容易连向到操作树，我们每次二分到哪个位置，直接在这个位置后面连上这个点就好了。但是发现操作树是动态的并不能二分，那么我们可以直接把栈中对应的位置直接改掉，并且修改一下记录的栈顶，这样就不用花时间删除后面的元素了。最后回溯的时候再改回去即可。发现在每个点对栈的修改是 $O(1)$ 的，总复杂度 $O(n \log n)$。
但是这个题不加快速输出就 T 飞了，加上就会有 $0.015s$ 的好成绩。（怀疑是LemonLime测读入时间的锅）
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define fi first
#define se second
#define db double
#define U unsigned
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
#define ll long long
namespace FASTIO{
const int S=(1<<23)+5;static char b[S],o[S],p[20],*H=b,*T=b,*O=o,*P;static int r,s,c;
inline char gc(){return H==T?T=(H=b)+fread(b,1,S,stdin):0,H!=T?*H++:-1;}
inline int rf(){s=0;for(;!isdigit(c=gc());s=c);
for(r=c^48;isdigit(c=gc());(r*=10)+=c^48);
return s^45?r:-r;}
inline ll rfl(){ll r;s=0;for(;!isdigit(c=gc());s=c);
for(r=c^48;isdigit(c=gc());(r*=10)+=c^48);
return s^45?r:-r;}
inline int ef(){return fwrite(o,1,O-o,stdout),O=o,0;}
inline int w(){return O-o>S-128?ef():0;}
inline void wf(int x,char e=10){for(x<0?*O++=45,x=-x:0,x?:*O++=48,P=p;x;*++P=x%10+48,x/=10);
for(;P!=p;*O++=*P--);e?*O++=e,w():0;}
inline void wfl(ll x,char e=10){for(x<0?*O++=45,x=-x:0,x?:*O++=48,P=p;x;*++P=x%10+48,x/=10);
for(;P!=p;*O++=*P--);e?*O++=e,w():0;}
inline void ws(const char *e){strcpy(O,e);O+=strlen(e);w();}
inline void wc(char e){*O++=e;w();}
}
using FASTIO::rf;using FASTIO::rfl;using FASTIO::ef;
using FASTIO::wf;using FASTIO::wfl;using FASTIO::ws;using FASTIO::wc;
const int MAXN = 1e6 + 5;
std::vector<int> G[MAXN];
int n,a[MAXN];
int stk[MAXN],tp[MAXN];
inline void dfs(int v){
int ps,bk;
if(v == 1){
stk[++tp[v]] = a[v];
}
else{
int l = 1,r = tp[v],ans = 0;
while(l <= r){
int mid = (l + r) >> 1;
if(stk[mid] >= a[v]) ans = mid,l = mid+1;
else r = mid-1;
}
tp[v] = ans+1;
ps = tp[v],bk = stk[ps];
stk[ps] = a[v];
}
for(auto x:G[v]){
tp[x] = tp[v];
dfs(x);
}
if(v != 1) stk[ps] = bk;
}
int main(){
freopen("suffix.in","r",stdin);
freopen("suffix.out","w",stdout);
n = rf();
FOR(i,2,n){
int f=rf();G[f].pb(i);
}
FOR(i,1,n) a[i] = rf();
dfs(1);
FOR(i,1,n) wf(tp[i],' ');wc('\n');ef();
return 0;
}B
长度为 $n$ 的序列 $a_i$，给定一个常数 $k$ ，问有多少个区间 $[l,r]$，满足 $\max_{i=l}^n\{a_i\} + \min_{i=l}^r \{a_i\} = k$。 $n \leq 10^6$。
经典题。分治，考虑跨过中点的所有区间，分类讨论最大值最小值在左边还是右边就好了。需要注意有多个最大值/最小值的时候要特判，我是强制最大值最小值在左边计算的。
这题感觉是全场最舒适的题了，不卡输出也没有写挂。
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
inline char nc(){
#define SIZE 1000000+3
static char buf[SIZE],*p1 = buf+SIZE,*p2 = buf+SIZE;
if(p1 == p2){
p1 = buf;p2 = buf+fread(buf,1,SIZE,stdin);
if(p1 == p2) return -1;
}
return *p1++;
#undef SIZE
}
template <typename T>
inline void read(T &x){
x = 0;int flag = 0;char ch = nc();
while(!isdigit(ch)){
if(ch == '-') flag = 1;
ch = nc();
}
while(isdigit(ch)){
x = (x<<1) + (x<<3) + (ch^'0');
ch = nc();
}
if(flag) x = -x;
}
const int MAXN = 1e6 + 5;
int n,x,a[MAXN];
LL ans = 0;
int mx[MAXN],mn[MAXN];
inline void work(int l,int r){
if(l > r) return;
if(l == r){
ans += (2*a[l]==x);
return;
}
int mid = (l + r) >> 1;
mx[mid] = -1e9;mn[mid] = 1e9;
FOR(i,mid+1,r){
mx[i] = std::max(mx[i-1],a[i]);
mn[i] = std::min(mn[i-1],a[i]);
}
mx[mid] = a[mid];mn[mid] = a[mid];
ROF(i,mid-1,l){
mx[i] = std::max(mx[i+1],a[i]);
mn[i] = std::min(mn[i+1],a[i]);
}
int i1=mid,i2=mid;// min/max
ROF(i,mid,l){
if(mx[i]+mn[i] != x) continue;
while(i1 < r && mn[i1+1] >= mn[i]) i1++;
while(i2 < r && mx[i2+1] <= mx[i]) i2++;
ans += std::min(i1,i2)-mid;
}
i1 = mid+1,i2 = mid+1;
FOR(i,mid+1,r){
if(mx[i]+mn[i] != x) continue;
while(i1 > l && mn[i1-1] > mn[i]) i1--;
while(i2 > l && mx[i2-1] < mx[i]) i2--;
ans += mid+1-std::max(i1,i2);
}
i2 = mid;int ll = mid+1,rr = mid;
ROF(i,mid,l){
while(i2 < r && mx[i2+1] <= mx[i]) i2++;
int d = x-mx[i];
if(d >= mn[i]) continue;
while(rr < r && mn[rr+1] >= d) ++rr;
if(rr == r && mn[rr] != d) break;
while(ll <= r && mn[ll] > d) ++ll;
if(ll <= rr && mn[ll] == d && mn[rr] == d) ans += std::max(0,std::min(rr,i2)-ll+1);
}
i1 = mid+1;ll = mid+1,rr = mid;
FOR(i,mid+1,r){
while(i1 > l && mx[i1-1] < mx[i]) i1--;
int d = x-mx[i];
if(d > mn[i]) continue;
while(ll > l && mn[ll-1] >= d) --ll;
if(ll == l && mn[ll] != d) break;
while(rr >= l && mn[rr] > d) --rr;
if(ll <= rr && mn[ll] == d && mn[rr] == d) ans += std::max(0,rr-std::max(i1,ll)+1);
}
work(l,mid);work(mid+1,r);
}
int main(){
freopen("interval.in","r",stdin);
freopen("interval.out","w",stdout);
read(n);read(x);
FOR(i,1,n) read(a[i]);
work(1,n);
printf("%lld\n",ans);
return 0;
}C
int B;
void init(int n)
{
ans=0;
for(int i=1;i<=n;i++)belong[i]=(i-1)/B+1;
}
void query(int l,int r)
{
if(belong[l]==belong[r])
{
for(int i=l;i<=r;i++)++ans;
return;
}
for(int i=belong[l]+1;i<belong[r];i++)++ans;
int R=belong[l]*B,L=(belong[r]-1)*B+1;
for(int i=L;i<=r;i++)++ans;
for(int i=l;i<=R;i++)++ans;
}
int main()
{
scanf("%d%d",&n,&m);init(n);
for(int i=1,l,r;i<=m;i++)
{
scanf("%d%d",&l,&r);
query(l,r);
}
cout<<ans<<endl;
}问这段代码在 $B = 1\ldots n$ 输出的值。$n,m \leq 10^6$。
首先写一下式子：假设当前的块长是 $B$，我们考虑区间 $[l,r]$ 的答案：
如果 $r-l+1 \leq B$，答案是 $r-l+1$。
否则答案是
$$ (\lfloor \frac{r-1}{B}\rfloor -\lfloor \frac{l-1}{B}\rfloor)+((\lfloor \frac{l-1}{B}\rfloor +1)\cdot B-(l-1))+(r-1-\lfloor \frac{r-1}{B}\rfloor\cdot B) $$
整理一下式子
$$ (\lfloor \frac{r-1}{B}\rfloor\cdot (1-B)+r)-(\lfloor \frac{l-1}{B}\rfloor \cdot (1-B)+l)+B $$
所以我们设 $f(x) = \lfloor \frac{x-1}{B} \rfloor \cdot (1-B)+x$，那么一个区间的答案就是 $f(r)-f(l)+B$。
所以我们现在可以把每个区间拆成两个点，一个贡献为正一个贡献为负，现在我们只要考虑如何计算 $f$ 的和就行了。
首先我们去枚举 $B$，然后可以发现本质不同的 $\lfloor \frac{x}{B} \rfloor$ 只有 $\lfloor \frac{n}{B} \rfloor$ 种，所以总共就是 $O(n \log n)$ 种。
所以我们可以去枚举所有的取值，然后相当于询问区间和（左端点为 $-1$，右端点为 $1$），用树状数组维护即可。
然后我们要处理 $r-l+1 \leq B$ 的部分：我们枚举到指定长度后就直接把长度 $=B$ 的区间在树状数组的贡献删掉，然后对应维护一下答案增量就行了。时间复杂度 $O(n \log^2 n)$ 但是由于是树状数组和调和级数的 $\log$ 所以很不满。具体做的时候你可以倒序枚举 $B$ 减少一点常数（虽然好像没有啥用，复杂度瓶颈在于询问不在于修改）
但是我考试的时候把 $m$ 写成 $n$ 了加上对拍的时候默认 $m=n$ 就挂零了。。要不然就过了
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define fi first
#define se second
#define db double
#define U unsigned
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
const int MAXN = 1e6 + 5;
#define ll long long
namespace FASTIO{
const int S=(1<<23)+5;static char b[S],o[S],p[20],*H=b,*T=b,*O=o,*P;static int r,s,c;
inline char gc(){return H==T?T=(H=b)+fread(b,1,S,stdin):0,H!=T?*H++:-1;}
inline int rf(){s=0;for(;!isdigit(c=gc());s=c);
for(r=c^48;isdigit(c=gc());(r*=10)+=c^48);
return s^45?r:-r;}
inline ll rfl(){ll r;s=0;for(;!isdigit(c=gc());s=c);
for(r=c^48;isdigit(c=gc());(r*=10)+=c^48);
return s^45?r:-r;}
inline int ef(){return fwrite(o,1,O-o,stdout),O=o,0;}
inline int w(){return O-o>S-128?ef():0;}
inline void wf(int x,char e=10){for(x<0?*O++=45,x=-x:0,x?:*O++=48,P=p;x;*++P=x%10+48,x/=10);
for(;P!=p;*O++=*P--);e?*O++=e,w():0;}
inline void wfl(ll x,char e=10){for(x<0?*O++=45,x=-x:0,x?:*O++=48,P=p;x;*++P=x%10+48,x/=10);
for(;P!=p;*O++=*P--);e?*O++=e,w():0;}
inline void ws(const char *e){strcpy(O,e);O+=strlen(e);w();}
inline void wc(char e){*O++=e;w();}
}
using FASTIO::rf;using FASTIO::rfl;using FASTIO::ef;
using FASTIO::wf;using FASTIO::wfl;using FASTIO::ws;using FASTIO::wc;
struct BIT{
#define lowbit(x) ((x)&(-(x)))
int tree[MAXN];
inline void add(int pos,int x){
pos += 2;
while(pos < MAXN){
tree[pos] += x;
pos += lowbit(pos);
}
}
inline int calc(int pos){
int res = 0;pos += 2;
while(pos){
res += tree[pos];
pos -= lowbit(pos);
}
return res;
}
inline int query(int l,int r){
return calc(r)-calc(l-1);
}
}bit;
int n,m;
std::vector<std::pair<int,int> > G[MAXN];
int main(){
freopen("block.in","r",stdin);
freopen("block.out","w",stdout);
// read(n);read(m);
n = rf();m = rf();
LL smx = 0,cnt = 0,sm = 0;
FOR(i,1,m){
int l=rf(),r=rf();//read(l);read(r);
// bit.add(r-1,1);bit.add(l-1,-1);
G[r-l+1].pb(MP(l,r));
sm += r-l+1;
}
// (1-b) (x-1)/B + x
std::vector<LL> out;
ROF(B,n,1){
LL ans = sm+smx;
for(int l = 0,r = B-1;l < n;l = r+1,r = l+B-1){
r = std::min(r,n-1);
ans += 1ll*(1-B)*(l/B)*bit.query(l,r);
}
ans += 1ll*cnt*B;
out.pb(ans);
FOR(i,0,(int)G[B].size()-1){
auto x = G[B][i];
sm -= x.se-x.fi+1;
bit.add(x.se-1,1);
bit.add(x.fi-1,-1);
smx += x.se-x.fi;
++cnt;
}
}
std::reverse(all(out));
for(auto x:out) wfl(x,' ');wc('\n');ef();
return 0;
}总结
对拍的时候所有变量请随机。
输出 $10^6$ 个数的时候如果程序很慢请考虑是不是输出的问题，不要卡常浪费时间了。（Linux 看 user time，Windows自己手动time一下）
One comment