一些关于二分和倍增的题，大体按照题目难度排序。
1. CF1951H Thanos Snap
简要题意
给定一个长为 \(2^n\) 的序列 \(a_0, a_1, \cdots, a_{2^n - 1}\)，对所有 \(t \in [1, n]\) 求解如下问题：
A 和 B 两人在序列 \(a\) 上博弈，一共进行 \(t\) 轮操作。每轮操作的流程如下：
- A 可以选择交换某两个不同元素的位置，或跳过本次操作。
- B 可以选择删去序列 \(a\) 左半部分或右半部分的元素。
定义得分为 \(a\) 中剩余元素的最大值。A 想要最大化得分，B 想要最小化得分。如果两人都采取最优策略，问最终得分是多少。
多测，\(1 \leq \sum 2^n \leq 2^{20}\)，\(1 \leq a_i \leq 2^n\)。
考虑二分答案，设二分出的答案为 \(p\)。那么问题转化为给定值 \(p\)，询问无论 B 如何操作，A 是否都能使得最终得分至少为 \(p\)。我们将大于等于 \(p\) 的元素标记为 \(1\)，小于 \(p\) 的元素标记为 \(0\)，那么 A 胜利等价于最终的序列中含有至少一个“1”。
显然最终的序列一定是以下 \(2^t\) 个区间之一：\(a[0, 2^{n - t}), a[2^{n - t}, 2^{n - t} \times 2), a[2^{n - t} \times 2, 2^{n - t} \times 3), \cdots, a[2^{n - t}(2^t - 1), 2^n)\)。对于某个最终的段，如果它某个时刻含有 \(s(s > 0)\) 个 1，那么我们一定会保留至少一个 1，只可能交换出去 \(s - 1\) 个 1，这样一定是不劣的。我们称能够交换出去的 1 为“自由的”。
考虑倒序维护操作序列，我们需要求出每个区间 \(a[l, l + 2^d)\) 是否是 A 必胜的。维护两个 DP 值：\(c[l, l + 2^d)\) 表示以该区间为初始区间，最终至少还有多少个区间没有 1；\(b[l, l + 2^d)\) 表示在保证有 1 的区间数量最大化的前提下，最终有多少个自由元（显然对于某个固定的区间，它们的差是个定值）。于是区间 \([l, l + 2^d)\) 是 A 必胜的当且仅当 \(c[l, l + 2^d) = 0\)。转移是简单的，只需将左右两半的 DP 值加起来，如果自由元和没有 1 的区间都有剩余那么就用一个自由元填充一个空区间。
对每个 \(t\) 都做一遍上述 DP，于是就做完了。由于每次 DP 只有 \(2n\) 种状态，因此时间复杂度为 \(\Theta(2^n n^2)\)。
代码
#include <cstdio>
const int N=20;
int n,a[1<<N],b[2<<N],c[2<<N],ls[1<<N];
// "b" denotes how many elements it can swap; "c" denotes how many elements it still need.
bool check(int d,int p){
int i,j,bl,br,cl,cr;
for(i=0;i<(1<<d);i++) ls[i]=0;
for(i=0;i<(1<<n);i++) ls[i>>n-d]+=(a[i]>=p);
for(i=0;i<(1<<d);i++)
if(!ls[i]) b[i+(1<<d)]=0,c[i+(1<<d)]=1;
else b[i+(1<<d)]=ls[i]-1,c[i+(1<<d)]=0;
for(i=d-1;i>=0;i--)
for(j=0;j<(1<<i);j++){
bl=b[(j<<1)+(1<<i+1)],br=b[(j<<1|1)+(1<<i+1)];
cl=c[(j<<1)+(1<<i+1)],cr=c[(j<<1|1)+(1<<i+1)];
if (cl>0&&br>0) br--,cl--;
else if(cr>0&&bl>0) bl--,cr--;
b[j+(1<<i)]=bl+br,c[j+(1<<i)]=cl+cr;
}
return !c[1];
}
int binary(int d){
int l=1,r=1<<n;
while(l<r){
int mid=(l+r+1)/2;
check(d,mid)?(l=mid):(r=mid-1);
}
return l;
}
int read(){
char ch; int x=0;
do ch=getchar();
while(ch<'0'||ch>'9');
while(ch>='0'&&ch<='9')
x=x*10+(ch-'0'),ch=getchar();
return x;
}
void write(int x){
char a[12]; int n=0,i;
do a[++n]=x%10+'0';
while((x/=10)>0);
for(i=n;i>0;i--) putchar(a[i]);
putchar(' ');
}
int main(){
// freopen("snap.in","r",stdin);
// freopen("snap.out","w",stdout);
int i,t;
for(t=read();t>0;t--){
for(n=read(),i=0;i<(1<<n);i++) a[i]=read();
for(i=1;i<=n;i++) write(binary(i));
putchar('\n');
}
// fclose(stdin);
// fclose(stdout);
return 0;
}
2. Gym103409H Popcount Words
简要题意
定义 \(s_i = \operatorname{popcount}(i) \bmod 2\) 表示二进制下 \(i\) 数位和的奇偶性。定义区间 \([l, r]\) 的 popcount 串为 \(w(l, r) = s_l s_{l + 1} \cdots s_{r - 1} s_r\)。
给定 \(n\) 个区间 \([l_1, r_1], [l_2, r_2], \cdots, [l_n, r_n]\)，记 0-1 串 \(S = w(l_1, r_1) + w(l_2, r_2) + \cdots + w(l_n, r_n)\)，其中“\(\texttt{+}\)”表示拼接。
再给定 \(q\) 次询问，每次询问给定模板 0-1 串 \(p_i\)，你需要求出有多少个 \(S\) 的子串 \(t\) 满足 \(p_i = t\)。
\(1 \leq n, q \leq 10^5\)，\(1 \leq l_i \leq r_i \leq 10^9\)，\(1 \leq \sum |p_i| \leq 5 \times 10^5\)。
对模板串建立 AC 自动机，记录每个串 \(p_i\) 的终止结点 \(b_i\)。将 \(S\) 在 AC 自动机上跑一遍匹配，那么答案即为经过每个 \(b_i\) 结点的次数。于是我们只需要统计经过每个结点的次数即可。然而 \(S\) 非常长，直接这么做复杂度会炸掉。
考虑 popcount 的经典性质，即对于 \(i \in [0, 2^d)\) 有 \(s_{i + 2^d} = s_i \oplus 1\)，原因是 \(i\) 和 \(i + 2^d\) 在二进制表示下只相差最高位的 \(1\)。记 \(W_{d, 0} = w(0, 2^d - 1), W_{d, 1} = w(2^d, 2^{d + 1} - 1)\)，那么显然有：
- \(W_{d, 0}\) 与 \(W_{d, 1}\) 长度均为 \(2^d\)，且每位上的值恰好相反。
- \(W_{d, 0}\) 以 \(0\) 开头，\(W_{d, 1}\) 以 \(1\) 开头。
- \(W_{d + 1, 0} = W_{d, 0} + W_{d, 1}\)，\(W_{d + 1, 1} = W_{d, 1} + W_{d, 0}\)。
- \(w(2^d i, 2^d(i + 1) - 1) = W_{d, s_i}\)。
前三条性质可以直接得出，最后一条性质可由第三条性质归纳得出。于是可以将每个 \(w(l, r)\) 拆成 \(\Theta(\log V)\) 个 \(W_i\) 相拼接的形式，因此整个串 \(S\) 也可以表示成 \(\Theta(n \cdot \log V)\) 个 \(W_i\) 相拼接的形式。这样我们就表示出了串 \(S\)。然而题目要求在 AC 自动机上做匹配，我们发现这还是很难完成。
事实上，运用类似的思想，我们也可以把匹配的过程进行压缩。预处理出 \(\mathrm{to}(u, d, 0 / 1)\) 表示从结点 \(u\) 开始匹配 0-1 串 \(W_{d, 0 / 1}\)，最终会走到哪个结点；匹配时，维护懒标记 \(\mathrm{tag}(u, d, 0 / 1)\) 表示从结点 \(u\) 开始匹配了多少次 \(W_{d, 0 / 1}\)。最后只需要把标记下放即可求出经过每个结点的次数，即将 \(\mathrm{tag}(u, d, 0 / 1)\) 下放到 \(\mathrm{tag}(u, d - 1, 0 / 1)\) 和 \(\mathrm{tag}(\mathrm{to}(u, d - 1, 0 / 1), d - 1, 1 / 0)\)，容易发现这是等价的。
本质上是利用 popcount 的倍增结构优化匹配的过程，时间复杂度为 \(\Theta(\sum |p_i| \cdot \log V)\)。
代码
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
const int N=100003,M=500003,P=31;
int n,q,al[N],ar[N],b[N]; char ch[M];
int tt=0,arr[N*P*2],brr[N*P*2];
namespace ACAM{
struct Node{
int son[2],ne,to[P][2];
long long tag[P][2],cnt;
vector<int> la;
}node[M];
int len_node=0;
int insert(int n,char a[M]){
int cur=0,i;
for(i=1;i<=n;i++){
if(!node[cur].son[a[i]-'0'])
node[cur].son[a[i]-'0']=++len_node;
cur=node[cur].son[a[i]-'0'];
}
return cur;
}
void build(){
int i,j,k,s1,s2; queue<int> dl;
for(node[0].ne=0,i=0;i<2;i++)
if(node[0].son[i]){
node[0].la.push_back(node[0].son[i]);
node[node[0].son[i]].ne=0;
dl.push(node[0].son[i]);
node[0].to[0][i]=node[0].son[i];
}
while(!dl.empty()){
s1=dl.front(),dl.pop();
for(i=0;i<2;i++){
s2=node[s1].son[i],j=node[s1].ne;
if(!s2){ node[s1].to[0][i]=node[j].to[0][i]; continue; }
while(j>0&&!node[j].son[i]) j=node[j].ne;
if(node[j].son[i]) j=node[j].son[i];
node[j].la.push_back(s2);
node[s2].ne=j,dl.push(s2);
node[s1].to[0][i]=s2;
}
}
for(i=1;i<P;i++)
for(j=0;j<=len_node;j++)
for(k=0;k<2;k++) node[j].to[i][k]=node[node[j].to[i-1][k]].to[i-1][!k];
}
void match(int n,int a[N*P*2],int b[N*P*2]){
int cur=0,i,j,k; node[cur].cnt++;
for(i=1;i<=n;i++){
node[cur].tag[a[i]][b[i]]++;
cur=node[cur].to[a[i]][b[i]];
}
for(i=P-1;i>0;i--)
for(j=0;j<=len_node;j++)
for(k=0;k<2;k++){
node[j].tag[i-1][k]+=node[j].tag[i][k];
node[node[j].to[i-1][k]].tag[i-1][!k]+=node[j].tag[i][k];
node[j].tag[i][k]=0;
}
for(i=0;i<=len_node;i++)
for(j=0;j<2;j++){
node[node[i].to[0][j]].cnt+=node[i].tag[0][j];
node[i].tag[0][j]=0;
}
}
void update(int u){
for(int i=0;i<node[u].la.size();i++)
update(node[u].la[i]);
if(u) node[node[u].ne].cnt+=node[u].cnt;
}
long long query(int u){
return node[u].cnt;
}
}
int read(){
char ch; int x=0;
do ch=getchar();
while(ch<'0'||ch>'9');
while(ch>='0'&&ch<='9')
x=x*10+(ch-'0'),ch=getchar();
return x;
}
void write(long long x){
char a[24]; int n=0,i;
do a[++n]=x%10+'0';
while((x/=10)>0);
for(i=n;i>0;i--) putchar(a[i]);
putchar('\n');
}
int main(){
// freopen("popcount.in","r",stdin);
// freopen("popcount.out","w",stdout);
int i,j,s1,s2,s3;
n=read(),q=read();
for(i=1;i<=n;i++)
al[i]=read(),ar[i]=read();
for(i=1;i<=q;i++){
gets(&ch[1]),s1=strlen(&ch[1]);
b[i]=ACAM::insert(s1,ch);
}
ACAM::build();
for(i=1;i<=n;i++){
s1=al[i],s2=ar[i]+1;
for(j=0;j<P&&s1+(1<<j)<=s2;j++)
if(s1>>j&1) tt++,arr[tt]=j,brr[tt]=__builtin_popcount(s1)&1,s1+=1<<j;
for(j=P-1;j>=0;j--)
if(s1+(1<<j)<=s2) tt++,arr[tt]=j,brr[tt]=__builtin_popcount(s1)&1,s1+=1<<j;
}
ACAM::match(tt,arr,brr),ACAM::update(0);
for(i=1;i<=q;i++) write(ACAM::query(b[i]));
// fclose(stdin);
// fclose(stdout);
return 0;
}
3. CF1129E Legendary Tree
简要题意
这是一道交互题。
交互库有一个 \(n\) 个结点的树。给定 \(n\)，你需要询问不超过 \(11111\) 次得知树的形态。询问方式为给出两个非空不交点集 \(S, T\) 和一个点 \(u\)，交互库会返回满足 \(s \in S, t \in T\) 且 \(u\) 在路径 \((s, t)\) 上的二元组 \((s, t)\) 的数量。
\(2 \leq n \leq 500\)。
随便钦定一个根（不妨令为 \(1\)），对于每个点 \(u\)，只需令 \(S = \{1\}, T = V \setminus \{1, u\}\) 即可得到 \(u\) 的子树大小。
题目要求我们求出每个点的儿子（等价于求出每个点的父亲），而一个点儿子的子树大小严格小于该点的子树大小，于是考虑按子树大小从小到大确定每个点的儿子（和父亲）。时刻维护当前结点 \(u\) 和已经枚举过的、还没有确定父亲的结点集合 \(P\)，而我们可以通过二分集合 \(P\) 找出 \(u\) 的一个儿子，具体方式为：对于集合 \(Q \subseteq P\)，\(Q\) 中存在 \(u\) 的儿子当且仅当询问 \(S = \{1\}, T = Q\) 时，返回的结果大于 \(0\)。
由于儿子总数只有 \(n - 1\) 个，每次找一个儿子需要 \(\Theta(\log n)\) 步，且最开始还要询问 \(n - 1\) 次确定每个点的子树大小，因此总共询问约 \(n \log n + n\) 次就能确定树的形态。
代码
#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
const int N=503;
int n,son[N],ls[N],fa[N],a[N],m=0,b[N];
bool cmp(const int& u,const int& v){
return son[u]<son[v];
}
int main(){
int i,j,l,r,s1;
scanf("%d",&n),son[1]=ls[1]=n-1;
if(n==2){ puts("ANSWER"),puts("1 2"); return 0; }
for(i=2;i<=n;i++){
printf("1\n1\n%d\n",n-2);
for(j=2;j<=n;j++)
if(j!=i) printf("%d ",j);
printf("\n%d\n",i),fflush(stdout);
scanf("%d",&son[i]),ls[i]=son[i];
}
for(i=1;i<n;i++) a[i]=i+1;
sort(a+1,a+n,cmp);
for(i=1;i<n;b[++m]=a[i++])
while(ls[a[i]]>0){
l=1,r=m; while(l<r){
int mid=(l+r)/2;
printf("1\n1\n%d\n",mid-l+1);
for(j=l;j<=mid;j++) printf("%d ",b[j]);
printf("\n%d\n",a[i]),fflush(stdout);
scanf("%d",&s1); (s1>0)?(r=mid):(l=mid+1);
}
swap(b[r],b[m]),fa[b[m]]=a[i];
ls[a[i]]-=son[b[m--]]+1;
}
puts("ANSWER");
for(i=1;i<=m;i++) fa[b[i]]=1;
for(i=2;i<=n;i++) printf("%d %d\n",i,fa[i]);
return 0;
}
4. CF1764G Doremy's Perfect DS Class
简要题意
这是一道交互题。
交互库有一个 \([1, n]\) 的排列 \(p\)，你需要在 \(30 / 25 / 20\) 次内找到 \(p\) 中 \(1\) 的位置。询问方式为：给出 \(l, r, k\)，交互库会返回 \(\lfloor \dfrac{p_l}{k} \rfloor, \lfloor \dfrac{p_{l + 1}}{k} \rfloor, \cdots, \lfloor \dfrac{p_r}{k} \rfloor\) 中不同数的个数。
\(3 \leq n \leq 1024\)。
G1. 如何保证询问不超过 \(30\) 次？
发现询问次数大概是 \(\Theta(\log n)\) 级别，考虑二分答案。那么每次我们需要在 \(3\) 步之内判断 \(1\) 到底在 \(\mathrm{mid}\) 的左边还是右边。
考虑取 \(k = 2\)，将所有值按 \(\lfloor \frac{p_i}{2} \rfloor\) 分组，这样做的好处是大部分组都包含两个元素，而 \(1\) 所在的组只包含 \(1\) 这一个元素，这样就能够方便地把 \(1\) 和其他数区分开了。
如果 \(n\) 是奇数，那么除 \(1\) 外的其他组都包含两个元素。显然需要先询问 \(l = 1, r = \mathrm{mid}, k = 2\) 和 \(l = \mathrm{mid} + 1, r = n, k = 2\) 得到左右两边的段数，然后做法就比较多了。一种方法是容斥得出跨越左右两边的段的数量，然后即可求出每一边完整段内的元素总数，由于只有 \(1\) 所在的段有奇数个元素，因此 \(1\) 一定在完整段元素总数为奇数的那一边。
如果 \(n\) 是偶数，那么除了 \(1\) 以外，还有 \(n\) 所在的组也只包含一个元素。套用刚才的做法，我们会发现最后两边得出的值一定是同奇偶性的：如果均为偶数，那么 \(1\) 和 \(n\) 在 \(\mathrm{mid}\) 的同侧；如果均为奇数，那么 \(1\) 和 \(n\) 分居 \(\mathrm{mid}\) 的两侧。此时我们无法确定 \(1\) 到底在 \(\mathrm{mid}\) 的那一侧。
但我们可以求出 \(n\) 在 \(\mathrm{mid}\) 的哪一侧：具体而言，对于一个长度大于等于 \(2\)的区间 \([l, r]\)，只需询问 \(k = n\)，此时 \(n\) 在该区间中等价于返回 \(2\)。由上述分析，我们可以由此推出 \(1\) 到底在 \(\mathrm{mid}\) 的哪一侧。
综上，对于不同奇偶性的 \(n\)，我们在 \(30\) 步之内一定能二分出 \(1\) 所在的位置。
代码（$q \leq 30$）
#include <cstdio>
int ask(int l,int r,int k){
printf("? %d %d %d\n",l,r,k),fflush(stdout);
int s1; scanf("%d",&s1); return s1;
}
int main(){
int n,l,r,s1,s2,s3;
scanf("%d",&n),l=1,r=n;
while(l<r){
int mid=(l+r)/2;
s3=ask(1,mid,2)+ask(mid+1,n,2)-(n/2+1);
s1=mid-s3,s2=(n-mid)-s3;
if(n&1) (s1&1)?(r=mid):(l=mid+1);
else if(mid>1){
s3=ask(1,mid,n);
((s1&1)==(s3==1))?(r=mid):(l=mid+1);
}else{
s3=ask(mid+1,n,n);
((s1&1)==(s3==2))?(r=mid):(l=mid+1);
}
}
printf("! %d\n",r),fflush(stdout);
return 0;
}
注意到当 \(n\) 为奇数时，询问次数已经小于等于 \(20\)，因此下文的优化主要针对 \(n\) 为偶数的情况。
G2. 如何保证询问不超过 \(25\) 次？
回顾一下我们二分的过程，发现我们并没有利用完所有信息，比如说二分时 \(\mathrm{mid}\) 左右两边的区间长度。结合两次询问的答案，事实上我们可以对左右两边分别容斥，直接得出每一边只有一个元素的段的数量。
如果两侧数量不同，那么 \(1, n\) 一定在单独的段较多的那一侧，因为剩下的段都是互相匹配的。我们没有必要再浪费一次操作判断 \(n\) 到底再哪一侧。
如果两侧数量相同，那么 \(1\) 和 \(n\) 分居 \(\mathrm{mid}\) 的两侧，看起来没法优化询问的数量了。但其实我们只需要对第一次这种操作做一遍询问，后面的操作中 \(n\) 在哪边其实已经确定了（由于二分的区间不断向里缩小，之前 \(n\) 在哪边现在 \(n\) 一定还在哪边）。因此对于这类操作只需要额外花费一次询问。
综上，对于 \(n\) 为偶数的情况，我们也能做到只花费 \(21\) 次询问就得到答案。
代码（$q \leq 21$）
#include <cstdio>
inline int ask(int l,int r,int k){
printf("? %d %d %d\n",l,r,k),fflush(stdout);
int s1; scanf("%d",&s1); return s1;
}
int main(){
int n,l,r,cur=-1,s1,s2,s3,s4;
scanf("%d",&n),l=1,r=n;
while(l<r){
int mid=(l+r)/2;
s1=ask(1,mid,2),s2=ask(mid+1,n,2);
s3=mid-s1,s4=n-mid-s2,s1-=s3,s2-=s4;
if(s1!=s2) (s1>s2)?(r=mid):(l=mid+1);
else{
if(cur==-1) cur=(mid>1)?(2-ask(1,mid,n)):(ask(mid+1,n,n)-1);
cur?(r=mid):(l=mid+1);
}
}
printf("! %d\n",r),fflush(stdout);
return 0;
}
G3. 如何保证询问不超过 \(20\) 次？
我们只需要再优化掉 \(1\) 次操作，但前面 \(k = n\) 的那次操作似乎已经优化到极致了。
我们发现如果二分的轮数卡满 \(\lceil \log n \rceil\) 次，那么最后一轮二分一定满足 \(r = l + 1, \mathrm{mid} = l\)。这轮二分有个优势，就是 \(\mathrm{mid}_1 = \mathrm{mid} - 1\) 和 \(\mathrm{mid}_2 = \mathrm{mid} + 1\) 的那 \(4\) 次操作在前面已经做完了。那么我们能不能一次询问就解决这轮二分呢？
如果此时还没确定 \(n\) 在 \([l, r]\) 的哪一侧，那么 \(l, r\) 这两个元素中一定有一个是 \(n\)。只需进行一次 \(k = n\) 的询问即可确定 \(n\) 到底在哪个位置，那么另一个就是 \(1\)。
否则，考虑 \([l, r]\) 中的另一个元素，与它匹配的元素要么在左侧要么在右侧，且会使得将 \(n\) 排除后该侧的单独段数量要多一些。由 G2 的做法，我们可以找出该元素所在的那一侧。不妨设它在左侧。设 \(s\) 是询问 \((1, l - 1, 2)\) 的答案，考虑询问 \((1, l, 2)\) 的答案 \(t\)，如果 \(p_l = 1\)，那么询问会多出一段，此时 \(t = s + 1\)；否则，该元素会与左侧的元素匹配，此时段数不变，即 \(t = s\)。据此可以分辨出元素 \(1\) 的位置。
综上，我们在 \(20\) 次操作内解决了该问题。
代码（$q \leq 20$）
#include <cstdio>
#include <iostream>
using namespace std;
inline int ask(int l,int r,int k){
printf("? %d %d %d\n",l,r,k),fflush(stdout);
int s1; scanf("%d",&s1); return s1;
}
int main(){
int n,l,r,cur=-1,s1,s2,s3,s4,pre1,pre2,suf1,suf2;
scanf("%d",&n),l=1,r=n,pre1=suf2=0,pre2=suf1=n/2+1;
while(r-l>!(n&1)){
int mid=(l+r)/2;
s1=ask(1,mid,2),s2=ask(mid+1,n,2);
s3=mid-s1,s4=n-mid-s2,s1-=s3,s2-=s4;
if(s1!=s2) (s1>s2)?(r=mid):(l=mid+1);
else{
if(cur==-1) cur=(mid>1)?(2-ask(1,mid,n)):(ask(mid+1,n,n)-1);
cur?(r=mid):(l=mid+1);
}
(r==mid)?(suf1=s1+s3):(pre1=s1+s3);
(r==mid)?(suf2=s2+s4):(pre2=s2+s4);
}
if(r==l+1)
if(cur==-1&&l>1) (ask(l-1,l,n)==1)?(r=l):(l=r);
else if(cur==-1) (ask(r,r+1,n)==1)?(l=r):(r=l);
else if(suf1==pre1+1) (ask(1,l,2)>pre1)?(r=l):(l=r);
else (ask(r,n,2)>suf2)?(l=r):(r=l);
printf("! %d\n",r),fflush(stdout);
return 0;
}
5. CF1707E Replace
简要题意
给定一个长为 \(n\)、值域为 \([1, n]\) 的序列 \(a\)。对于 \(l \leq r\)，定义区间函数 \(f([l, r]) = [\min_{k = l}^r a_k, \max_{k = l}^r a_k]\)；并递归地定义 \(f^0([l, r]) = [l, r]\)，\(f^k([l, r]) = f(f^{k - 1}([l, r])) (k > 0)\)。
\(q\) 次询问，每次给定区间 \([l_i, r_i]\)，你需要求出最小的自然数 \(k\) 使得 \(f^k([l_i, r_i]) = [1, n]\)。如果不存在这样的 \(k\)，输出 \(-1\)。
\(1 \leq n, q \leq 10^5\)，\(1 \leq a_i \leq n\)。
显然若 \(l_i = 1, r_i = n\) 那么答案为 \(0\)，若 \(l_i = r_i\) 一定无解。对于其他情况，只有序列 \(a\) 中同时存在 \(1\) 和 \(n\) 时才可能有解。下文中我们默认讨论这种情况。
我们发现此时一定有 \(f([1, n]) = [1, n]\)，这说明只要 \(f^k([l_i, r_i]) = [1, n]\)，那么对于所有满足 \(x \geq k\) 的自然数 \(x\) 均有 \(f^x([l_i, r_i]) = [1, n]\)。又由于如果我们在映射的过程中经过了同一个区间两次，那么映射的过程必然会陷入循环，因此答案的上界最大是 \(n^2\)。于是答案具有可二分性，答案 \(k \leq \mathrm{mid}\) 当且仅当 \(f^\mathrm{mid}([l_i, r_i]) = [1, n]\)。此时一个很自然的想法是对每个区间 \([l, r]\)，预处理出倍增数组 \(g(l, r, k) = f^{2^k}([l, r])\)，查询时我们只需要倍增地进行映射即可。但是由于区间有 \(\Theta(n^2)\) 个，这样预处理的复杂度会炸掉，因此我们需要观察一些性质。
我们断言如果两个区间 \([l_1, r_1]\) 和 \([l_2, r_2]\) 有交，那么区间 \(f([l_1, r_1])\) 和 \(f([l_2, r_2])\) 一定有交，原因是：若 \(p\) 同时在区间 \([l_1, r_1]\) 和 \([l_2, r_2]\) 内，则 \(a_p\) 必然同时在区间 \(f([l_1, r_1])\) 和 \(f([l_2, r_2])\) 内。同理，我们有 \(f([l_1, r_1] \cup [l_2, r_2]) = f([l_1, r_1]) \cup f([l_2, r_2])\)，并可以递归地证明 \(f^k([l_1, r_1] \cup [l_2, r_2]) = f^k([l_1, r_1]) \cup f^k([l_2, r_2])\)。
因此我们只需要预处理出 \([1, 2], [2, 3], \cdots, [n - 1, n]\) 这 \(n - 1\) 个“单位”区间的倍增数组，其他区间无论是区间本身还是倍增数组均可以拆分成若干个单位区间（或其倍增数组）的并，于是预处理的复杂度便降了下来。查询时只需用 ST 表维护区间左右端点即可保证时间复杂度，这样我们就做完了。
时间复杂度为 \(\Theta(n \log^2 n + q \log n)\)，可以通过。空间复杂度为 \(\Theta(n \log^2 n)\)，但如果把所有询问离线下来一起倍增即可降至 \(\Theta(n \log n)\)。注意特判边界情况。
代码
#include <cstdio>
#include <iostream>
using namespace std;
const int N=100003,log_N=18,log_P=36;
struct Question{
int l,r;
}qu[N];
int n,q,a[N],al[N][log_P+1],ar[N][log_P+1];
long long ans[N];
namespace ST{
int minn[log_N][N],maxn[log_N][N],lgt[N];
void init_ST(int d){
for(int i=2;i<n;i++) lgt[i]=lgt[i>>1]+1;
for(int i=1;i<n;i++) minn[0][i]=al[i][d];
for(int i=1;i<n;i++) maxn[0][i]=ar[i][d];
for(int i=1;i<log_N;i++)
for(int j=1;j+(1<<i)-1<n;j++){
minn[i][j]=min(minn[i-1][j],minn[i-1][j+(1<<i-1)]);
maxn[i][j]=max(maxn[i-1][j],maxn[i-1][j+(1<<i-1)]);
}
}
int query_minn(int l,int r){
if(l>r||l<0||r<0) return n+1;
int d=lgt[r-l+1];
return min(minn[d][l],minn[d][r-(1<<d)+1]);
}
int query_maxn(int l,int r){
if(l>r||l<0||r<0) return -1;
int d=lgt[r-l+1];
return max(maxn[d][l],maxn[d][r-(1<<d)+1]);
}
}
int main(){
// freopen("replace.in","r",stdin);
// freopen("replace.out","w",stdout);
int i,j,s1,s2; scanf("%d%d",&n,&q);
for(i=1;i<=n;i++) scanf("%d",&a[i]);
for(i=1;i<n;i++)
al[i][0]=min(a[i],a[i+1]),ar[i][0]=max(a[i],a[i+1]);
for(i=1;i<=log_P;i++)
for(ST::init_ST(i-1),j=1;j<n;j++){
al[j][i]=ST::query_minn(al[j][i-1],ar[j][i-1]-1);
ar[j][i]=ST::query_maxn(al[j][i-1],ar[j][i-1]-1);
}
if(n==1){
for(i=1;i<=q;i++) puts("0");
return 0;
}
for(i=1;i<=q;i++)
scanf("%d%d",&qu[i].l,&qu[i].r);
ST::init_ST(log_P);
for(i=1;i<=q;i++)
if(qu[i].l==qu[i].r) ans[i]=-1;
else if(qu[i].l==1&&qu[i].r==n) continue;
else if(ST::query_minn(qu[i].l,qu[i].r-1)>1) ans[i]=-1;
else if(ST::query_maxn(qu[i].l,qu[i].r-1)<n) ans[i]=-1;
for(i=log_P-1;i>=0;i--)
for(ST::init_ST(i),j=1;j<=q;j++){
if(ans[j]==-1||qu[j].l==1&&qu[j].r==n) continue;
s1=ST::query_minn(qu[j].l,qu[j].r-1);
s2=ST::query_maxn(qu[j].l,qu[j].r-1);
if(s1>1||s2<n) qu[j].l=s1,qu[j].r=s2,ans[j]+=1ll<<i;
}
for(i=1;i<=q;i++)
if((qu[i].l>1||qu[i].r<n)&&ans[i]>=0) ans[i]++;
for(i=1;i<=q;i++) printf("%lld\n",ans[i]);
// fclose(stdin);
// fclose(stdout);
return 0;
}
6. CF1034D Intervals of Intervals
简要题意
数轴上有 \(n\) 条线段，第 \(i\) 条为 \([a_i, b_i)\)。再定义一个区间 \([l, r] (1 \leq l \leq r \leq n)\) 的价值是第 \(l\) 条线段到第 \(r\) 条线段的并的长度。
给定 \(k\)，求选择 \(k\) 个互不相同的区间后，其价值和的最大值。
\(1 \leq n \leq 3 \times 10^5\)，\(1 \leq k \leq \min\{ \frac{n(n + 1)}{2}, 10^9 \}\)。
显然我们应该优先选择价值更大的区间。考虑二分求出第 \(k\) 大的价值，于是问题转化为两部分：给定 \(x\)，求价值大于等于 \(x\) 的区间数量；以及大于等于 \(x\) 的价值之和。
显然两个问题是本质相同的，于是我们只需要关心第一个问题怎么做。对于一个固定的区间右端点 \(r\)，显然左端点越小该区间的价值就越大，于是我们只需要求出 \(f(r)\) 表示最大的左端点 \(l\) 满足区间 \([l, r]\) 的价值不小于 \(x\)。那么区间的数量即为 \(\sum_{i = 1}^n f(i)\)。又发现 \(f(i)\) 单调不减，因此考虑双指针求出每个 \(f(i)\) 的值。具体地，我们需要在线地维护区间 \([l, r]\) 和它的价值，即在右端加入一条线段和从左端删除线段后，我们需要快速求出价值的变化量。
考虑对数轴上每个点 \(i\)，维护覆盖该点的最后一条线段。相当于给第 \(i\) 条线段赋颜色 \(i\)，每个点上初始的颜色为 \(0\)；加入一条线段相当于区间颜色覆盖；删除一条线段 \(i\) 相当于将当前所有颜色为 \(i\) 的点颜色都置成 \(0\)。这可以用颜色段均摊的技巧维护：称一段颜色相同的点为一个颜色段，用一个 set 维护每个颜色段的两端；加入一条线段时，分裂两端点所在的颜色段，并合并两端点之间的所有颜色段；删除一条线段时，我们不用真的修改颜色段，事实上我们只需要维护当前区间 \([l, r]\) 的左端点 \(l\)，那么所有标记的颜色小于 \(l\) 的点真实颜色均为 \(0\)。由于每次操作最多增加 \(2\) 个颜色段，且每遍历一个颜色段必然会合并一次，因此总共最多修改 \(\Theta(n)\) 次颜色段。此时时间复杂度为 \(\Theta(n \log^2 n)\)，无法通过。
但我们发现每次二分的过程中修改颜色段的过程都是确定的，因此我们可以在二分之前就预处理出每次加入一条线段会修改哪些颜色段。相当于把 set 的 \(\log\) 提到二分外，这样每次二分的时候只需要 \(\Theta(1)\) 修改颜色段。时间复杂度降至 \(\Theta(n \log n)\)，稍微卡常即可通过。
代码
#include <algorithm>
#include <cstdio>
#include <set>
#include <vector>
using namespace std;
const int N=600003,P=(int)1e9+10;
struct Range{
int l,r;
}a[N];
struct Operation{
int opt,l,r; // "opt = 1/2": Insert/Erase Range [l, r).
};
long long w[N];
int n,m,p,bel[N],b[N];
vector<Operation> op[N];
vector<int> alls; set<int> st;
int binary1(int x){
int l=0,r=alls.size();
while(l<r){
int mid=(l+r)/2;
(alls[mid]>=x)?(r=mid):(l=mid+1);
}
return r;
}
long long solve(int x){
int i,j,k,s1,s2,opt,l,r;
long long sum=0,ans=0;
for(i=1;i<=p+1;i++) bel[i]=0;
for(i=1;i<=n;i++) w[i]=0;
for(i=j=1;i<=n;i++){
for(k=0;k<op[i].size();k++){
opt=op[i][k].opt,l=op[i][k].l,r=op[i][k].r;
if(opt==2) s1=bel[l]; if(s1<j) continue;
bel[l]=(opt==2)?0:s1,s2=alls[r-1]-alls[l-1];
s2*=(opt==2)?-1:1,w[s1]+=s2,sum+=s2;
}
l=a[i].l,r=a[i].r,s2=alls[r-1]-alls[l-1];
bel[l]=i,w[i]+=s2,sum+=s2;
while(sum>=x) sum-=w[j++];
b[i]=j-1,ans+=j-1;
}
return ans;
}
int binary2(int l,int r){
while(l<r){
int mid=(l+r+1)/2;
(solve(mid)>=m)?(l=mid):(r=mid-1);
}
return l;
}
inline void change(int i,int j,int l,int r,int mul,long long& sum1,long long& sum2){
int s1=(alls[r-1]-alls[l-1])*mul;
w[i]+=s1,(i>j)?(sum1+=s1):(sum2+=(long long)s1*i);
}
int read(){
char ch; int x=0;
do ch=getchar();
while(ch<'0'||ch>'9');
while(ch>='0'&&ch<='9')
x=x*10+(ch-'0'),ch=getchar();
return x;
}
int main(){
// freopen("interval.in","r",stdin);
// freopen("interval.out","w",stdout);
set<int>::iterator sl,sr,tl,tr,j1,j2;
int i,j,k,s1,s2,opt,l,r;
long long ans=0,sum1,sum2;
n=read(),m=read();
for(i=1;i<=n;i++){
a[i].l=read(),a[i].r=read();
alls.push_back(a[i].l);
alls.push_back(a[i].r);
}
sort(alls.begin(),alls.end());
alls.erase(unique(alls.begin(),alls.end()),alls.end());
for(i=1;i<=n;i++) a[i].l=binary1(a[i].l)+1;
for(i=1;i<=n;i++) a[i].r=binary1(a[i].r)+1;
p=alls.size(),st.insert(1),st.insert(p+1);
for(i=1;i<=n;i++){
sl=st.upper_bound(a[i].l);
sr=st.lower_bound(a[i].r);
if((sl--)==sr){
op[i].push_back({2,*sl,*sr});
if((*sl)<a[i].l) op[i].push_back({1,*sl,a[i].l});
if((*sr)>a[i].r) op[i].push_back({1,a[i].r,*sr});
st.insert(a[i].l),st.insert(a[i].r); continue;
}
tl=sl,++tl,tr=sr,--tr;
op[i].push_back({2,*sl,*tl});
if((*sl)<a[i].l) op[i].push_back({1,*sl,a[i].l});
op[i].push_back({2,*tr,*sr});
if((*sr)>a[i].r) op[i].push_back({1,a[i].r,*sr});
for(j1=j2=tl,++j2;j2!=sr;j1=j2,++j2)
op[i].push_back({2,*j1,*j2});
st.erase(tl,sr),st.insert(a[i].l),st.insert(a[i].r);
}
s1=binary2(0,P),ans-=(solve(s1)-m)*s1;
for(i=1;i<=p+1;i++) bel[i]=0;
for(i=1;i<=n;i++) w[i]=0;
for(i=1,j=0,sum1=sum2=0;i<=n;i++){
for(k=0;k<op[i].size();k++){
opt=op[i][k].opt,l=op[i][k].l,r=op[i][k].r;
if(opt==2) s1=bel[l]; bel[l]=(opt==2)?0:s1;
s2=alls[r-1]-alls[l-1],s2*=(opt==2)?-1:1;
w[s1]+=s2,(s1>j)?(sum1+=s2):(sum2+=(long long)s2*s1);
}
l=a[i].l,r=a[i].r,s2=alls[r-1]-alls[l-1];
bel[l]=i,w[i]+=s2,(i>j)?(sum1+=s2):(sum2+=(long long)s2*i);
while(j<b[i]) j++,sum1-=w[j],sum2+=(long long)w[j]*j;
ans+=sum1*b[i]+sum2;
}
printf("%lld",ans);
// fclose(stdin);
// fclose(stdout);
return 0;
}
7. 洛谷 P7447 [Ynoi2007] rgxsxrs
简要题意
给定一个长为 \(n\) 的序列 \(a\)，需要实现 \(q\) 次操作，操作有以下两种：
- \(1~l~r~x\)：将区间 \([l, r]\) 中所有大于 \(x\) 的元素减去 \(x\)；
- \(2~l~r\)：询问区间 \([l, r]\) 中所有元素的和、最小值、最大值。
强制在线，\(1 \leq n, q \leq 5 \times 10^5\)，\(1 \leq x, a_i \leq 10^9\)。注意本题特殊的空间限制 \(64 \text{MB}\)。
显然有一个很暴力的思路：我们直接用线段树维护这些信息，那么询问的时间复杂度就能做到 \(\Theta(q \log n)\)。修改时，如果所有元素都不超过 \(x\) 就返回；如果所有元素都超过 \(x\) 就打上区间减的标记；否则我们无法快速判断该节点到底有多少元素大于 \(x\)，于是我们将修改操作细化，继续向左右儿子递归下去。这样修改的时间复杂度是 \(\Theta(qn)\) 的，不可接受。
我们希望尽可能地减小时间复杂度。注意到此时瓶颈在对值域的判定上，于是考虑在值域上分块，对每一块分别建立一棵线段树。这样我们就只用在一个块的线段树上细化修改操作，其他块要么值域被 \([1, x]\) 包含，要么与它不交，都可以通过懒标记解决，于是我们有效地降低了时间复杂度。我们称在这个块上进行的修改操作为“特殊操作”。注意一次操作后某些元素可能已经不属于它所处的值域段，因此我们还需要暴力给它们“换块”。设块数为 \(s\)，由于单个元素值的变化是单调的，因此每个元素至多执行 \(s\) 次换块操作，换块的复杂度为 \(\Theta(ns \log n)\)，与询问和修改大部分块的复杂度 \(\Theta(qs \log n)\) 同阶，瓶颈仍然在特殊操作上。
接下来是本题最为关键的性质：若一个值域段为 \([l_i, r_i]\)，那么每个元素至多只会在这个块上进行 \(\Theta(\frac{r_i}{l_i})\) 次操作。原因很简单，考虑一次特殊操作必然满足 \(x \in [l_i, r_i]\)，因此一次操作后每个元素的值至少会减去 \(l_i\)，因此 \(\frac{r_i}{l_i}\) 次操作后该元素就不属于这个值域段了。这个性质看似不起眼，但事实上它说明了复杂度已被优化至足够优秀的 \(\Theta((n + q) \log n \cdot \sum_{i = 1}^s \frac{r_i}{l_i})\)。接下来我们只需要构造一组分块方案使得 \(\sum_{i = 1}^s \frac{r_i}{l_i}\) 尽可能小，那么做法已经很明显了：我们按照值域倍增分块，取第 \(i\) 块为 \([2^{i - 1}, 2^i)\)，总复杂度即为 \(\Theta((n + q) \log n \log V)\)。
这样做的一个问题就是空间复杂度为 \(\Theta(n \log V)\)，由于本题卡空间因此不可接受。套路地，我们考虑对线段树底层分块，设块长为 \(B = \Theta(\log V)\)，在线段树建树和进行操作的过程中，一旦当前区间的长度小于等于 \(B\)，我们就不再继续向下递归，而是在当前区间上暴力执行操作。于是空间复杂度被优化至 \(\Theta(n)\)。
另一个问题就是加上底层分块后原先的做法会被卡常。考虑改变一下倍增的底数，取第 \(i\) 块为 \([p^{i - 1}, p^i)\)。感性理解一下，由于加了底层分块，此时因为常数问题取 \(p = 2\) 程序的效率不再是最优的，于是乱调参即可。时间复杂度为 \(\Theta((np + q) \log n \log_p V)\)。
代码
#include <cstdio>
#include <iostream>
using namespace std;
const int N=500003,B=32,log_V=6,S=32,P=32770,modANS=1<<20;
const int PIN=(int)2e9+10;
int n,a[N],key[N],powB[log_V];
struct SGT{
struct Node{
int l,r,cnt,maxn,minn,minu,sub;
long long sum;
}node[P]; int d;
friend Node operator+(Node l,Node r){
Node ans={l.l,r.r,0,-1,PIN,-1,0,0};
ans.cnt=l.cnt+r.cnt,ans.sum=l.sum+r.sum;
ans.maxn=max(l.maxn,r.maxn),ans.minn=min(l.minn,r.minn);
ans.minu=((ans.minn==l.minn)?l:r).minu;
return ans;
}
friend void operator+=(Node& a,Node b){ a=a+b; }
void init_SGT(int _d){ d=_d; }
void update(int u,int x){
if(!node[u].cnt) return ;
node[u].maxn-=x,node[u].minn-=x,node[u].sub+=x;
node[u].sum-=(long long)x*node[u].cnt;
}
void push_up(int u){
node[u]=node[u*2]+node[u*2+1];
}
void push_down(int u){
update(u*2 ,node[u].sub);
update(u*2+1,node[u].sub);
node[u].sub=0;
}
void rebuild(Node& ans,int x=0){
ans.sum=0,ans.maxn=-1,ans.minn=PIN,ans.minu=-1,ans.cnt=0;
for(int i=ans.l;i<=ans.r;i++){
if(key[i]!=d) continue;
ans.sum+=a[i]-x,ans.cnt++,ans.maxn=max(ans.maxn,a[i]-x);
if(a[i]-x<ans.minn) ans.minn=a[i]-x,ans.minu=i;
}
}
void build(int u,int l,int r){
node[u].l=l,node[u].r=r,node[u].sub=0,node[u].minu=l;
if(r-l+1<=S) rebuild(node[u]);
else{
int mid=(l+r)/2;
build(u*2 ,l,mid );
build(u*2+1,mid+1,r);
push_up(u);
}
}
void modify_sub(int u,int l,int r,int x){
if(node[u].maxn<=x) return ;
if(node[u].l>=l&&node[u].r<=r&&node[u].minn>x) update(u,x);
else if(node[u].r-node[u].l+1<=S){
for(int i=node[u].l;i<=node[u].r;i++)
if(key[i]==d) a[i]-=node[u].sub;
for(int i=node[u].l;i<=node[u].r;i++)
if(key[i]==d&&i>=l&&i<=r&&a[i]>x) a[i]-=x;
node[u].sub=0,rebuild(node[u]);
}else{
push_down(u);
int mid=(node[u].l+node[u].r)/2;
if(l<=mid) modify_sub(u*2 ,l,r,x);
if(r> mid) modify_sub(u*2+1,l,r,x);
push_up(u);
}
}
void modify_act(int u,int k){
if(node[u].r-node[u].l+1<=S){
for(int i=node[u].l;i<=node[u].r;i++)
if(i!=k&&key[i]==d) a[i]-=node[u].sub;
node[u].sub=0,rebuild(node[u]);
}else{
push_down(u);
int mid=(node[u].l+node[u].r)/2;
modify_act(u*2+(k>mid),k);
push_up(u);
}
}
Node query(int u,int l,int r){
if(node[u].l>=l&&node[u].r<=r) return node[u];
if(node[u].r-node[u].l+1<=S){
Node ans={max(node[u].l,l),min(node[u].r,r)};
rebuild(ans,node[u].sub); return ans;
}
int mid=(node[u].l+node[u].r)/2; push_down(u);
if(r<=mid) return query(u*2 ,l,r);
if(l> mid) return query(u*2+1,l,r);
return query(u*2,l,r)+query(u*2+1,l,r);
}
}sgt[log_V];
int read(){
char ch; int x=0;
do ch=getchar();
while(ch<'0'||ch>'9');
while(ch>='0'&&ch<='9')
x=x*10+(ch-'0'),ch=getchar();
return x;
}
template<typename T>
void write(T x,char ch){
char a[24]; int n=0,i;
do a[++n]=x%10+'0',x/=10; while(x>0);
for(i=n;i>0;i--) putchar(a[i]);
putchar(ch);
}
int main(){
// freopen("rgxsxrs.in","r",stdin);
// freopen("rgxsxrs.out","w",stdout);
int i,j,q,opt,l,r,x,ans=0,s1,s2;
SGT::Node s3; n=read(),q=read();
for(i=1,powB[0]=1;i<log_V;i++)
powB[i]=powB[i-1]*B;
for(i=1;i<=n;i++) a[i]=read();
for(i=1;i<=n;i++)
for(key[i]=log_V-1;powB[key[i]]>a[i];key[i]--);
for(i=0;i<log_V;i++)
sgt[i].init_SGT(i),sgt[i].build(1,1,n);
for(i=1;i<=q;i++){
opt=read(),l=read()^ans,r=read()^ans;
switch(opt){
case 1:
x=read()^ans;
for(j=0;j<log_V;j++)
sgt[j].modify_sub(1,l,r,x);
for(j=log_V-1;j>0;j--)
while((s1=sgt[j].query(1,1,n).minn)<powB[j]){
s2=sgt[j].query(1,1,n).minu,key[s2]--,a[s2]=s1;
sgt[j-1].modify_act(1,s2),sgt[j].modify_act(1,s2);
}
break;
case 2:
s3=sgt[0].query(1,l,r);
for(j=1;j<log_V;j++) s3+=sgt[j].query(1,l,r);
write(s3.sum,' '),write(s3.minn,' '),write(s3.maxn,'\n');
ans=s3.sum%modANS;
}
}
// fclose(stdin);
// fclose(stdout);
return 0;
}
8. 洛谷 P8987 [北大集训 2021] 简单数据结构
简要题意
给定长为 \(n\) 的序列 \(a\)。\(q\) 次操作，操作有以下三种：
- \(1~v\)：将所有 \(a_i\) 变为 \(\min\{a_i, v\}\)。
- \(2\)：将所有 \(a_i\) 变为 \(a_i + i\)。
- \(3~l~r\)：询问 \(\sum_{i = l}^r a_i\) 的值。
\(2 \leq n, q \leq 2 \times 10^5\)，\(0 \leq a_i, v \leq 10^{12}\)。
我们称一个元素执行过某次操作当且仅当这次操作后该元素的值发生了变化。
如果 \(a_i\) 初始均为 \(0\)，那么维护方法是简单的：观察到 \(a_i\) 始终单调不减，因此三个操作分别相当于区间赋值、区间加、区间求和，使用一棵线段树即可。
那么 \(a_i\) 有给定的初值怎么办呢？稍微分讨一下即可发现，在任意时刻，对此时所有执行过操作 1 的项，这些项之间保持单调不减的关系。即若 \(i < j\) 且 \(a_i, a_j\) 都执行过操作 1，那么必有 \(a_i \leq a_j\)。于是不妨将这些项提出来用一棵线段树维护，该线段树需要支持：单点激活、区间赋值、区间加、区间求和，使用与上面类似的维护方式即可。
问题转化成求出每个元素第一次执行操作 \(1\) 的时间。设 \(b_j\) 表示操作 \([1, j]\) 中操作 2 的数量，那么问题相当于对元素 \(a_i\)，求出最小的 \(j\) 使得 \(i \cdot b_j + a_i > v_j\)。发现这个式子类似于一次函数，考虑将其转化到平面直角坐标系上，那么问题相当于对元素 \(a_i\)，求出最小的 \(j\) 使得点 \((b_j, v_j)\) 在直线 \(y = ix + a_i\) 下方。
考虑整体二分，那么问题转化为给定一堆点和一堆直线，你需要对每条直线求出是否存在某个点在该直线下方。与斜率优化 DP 类似，考虑维护这些点的下凸壳，那么查询相当于对一些实数 \(k\)，求出与凸壳相切且斜率为 \(k\) 的直线的截距是多少，那么原问题即可转化为简单的比大小问题。由于点的横坐标 \(b_j\) 与查询直线的斜率 \(i\) 均单调不减，使用队列维护凸包即可。
时间复杂度为 \(\Theta(n \log n)\)。
代码
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
const int N=200003;
const long long PIN=1e18,NIN=-1e18;
struct Question{
int opt,l,r;
long long x;
}qu[N];
struct Checkmin{
int p,b; long long v;
}op[N];
struct Point{
long long x,y;
};
double getk(Point u,Point v){
if(u.x==v.x) return (u.y<v.y)?PIN:NIN;
return (double)(v.y-u.y)/(v.x-u.x);
}
int n,m,q; long long a[N];
vector<int> ls,chg[N];
inline int lowbit(int x){ return x&-x; }
namespace Hull{
Point a[N]; int hh,tt;
void clear(){ hh=1,tt=0; }
void push(Point u){
while(hh<tt&&getk(a[tt],u)<=getk(a[tt-1],a[tt])) tt--;
a[++tt]=u;
}
Point query(int k){
while(hh<tt&&getk(a[hh],a[hh+1])<=k) hh++;
return a[hh];
}
}
void solve(int l,int r,vector<int>& alls){
if(l==r){ chg[op[l].p].swap(alls); return ; }
int mid=(l+r)/2,i; Point s1; Hull::clear();
for(i=l;i<=mid;i++) Hull::push({op[i].b,op[i].v});
vector<int> sonl,sonr;
for(i=0;i<alls.size();i++){
s1=Hull::query(alls[i]);
((s1.y-alls[i]*s1.x<=a[alls[i]])?sonl:sonr).push_back(alls[i]);
}
alls.clear(),alls.shrink_to_fit();
solve(l,mid,sonl),solve(mid+1,r,sonr);
}
namespace SGT{
struct Node{
int l,r,cnt,add,minu,maxu; bool ned;
long long sumu,sumx,minn,maxn,chg;
}node[N*3];
void update_chg(int u,long long x){
if(!node[u].cnt) return ;
node[u].ned=1,node[u].chg=x,node[u].add=0;
node[u].minn=node[u].maxn=x,node[u].sumx=x*node[u].cnt;
}
void update_add(int u,int x){
if(!node[u].cnt) return ;
node[u].add+=x,node[u].sumx+=node[u].sumu*x;
node[u].minn+=(long long)x*node[u].minu;
node[u].maxn+=(long long)x*node[u].maxu;
}
void push_up(int u){
node[u].cnt =node[u*2].cnt +node[u*2+1].cnt ;
node[u].sumu=node[u*2].sumu+node[u*2+1].sumu;
node[u].sumx=node[u*2].sumx+node[u*2+1].sumx;
node[u].minu=min(node[u*2].minu,node[u*2+1].minu);
node[u].maxu=max(node[u*2].maxu,node[u*2+1].maxu);
node[u].minn=min(node[u*2].minn,node[u*2+1].minn);
node[u].maxn=max(node[u*2].maxn,node[u*2+1].maxn);
}
void push_down(int u){
if(node[u].ned){
update_chg(u*2 ,node[u].chg);
update_chg(u*2+1,node[u].chg);
node[u].ned=0;
}
if(node[u].add!=0){
update_add(u*2 ,node[u].add);
update_add(u*2+1,node[u].add);
node[u].add=0;
}
}
void build(int u,int l,int r){
node[u]={l,r,0,0,n+1,-1,0,0,0,PIN,NIN,-1};
if(l<r){
int mid=(l+r)/2;
build(u*2 ,l,mid );
build(u*2+1,mid+1,r);
}
}
void modify_act(int u,int k,long long x){
if(node[u].l==node[u].r) node[u]={k,k,1,0,k,k,0,k,x,x,x,-1};
else{
int mid=(node[u].l+node[u].r)/2; push_down(u);
modify_act(u*2+(k>mid),k,x); push_up(u);
}
}
void modify_chk(int u,long long x){
if(!node[u].cnt||node[u].maxn<=x) return ;
if(node[u].minn>=x) update_chg(u,x);
else{
int mid=(node[u].l+node[u].r)/2; push_down(u);
modify_chk(u*2,x),modify_chk(u*2+1,x),push_up(u);
}
}
void modify_add(){ update_add(1,1); }
long long query(int u,int l,int r){
if(node[u].l>=l&&node[u].r<=r) return node[u].sumx;
int mid=(node[u].l+node[u].r)/2; push_down(u);
if(r<=mid) return query(u*2 ,l,r);
if(l> mid) return query(u*2+1,l,r);
return query(u*2,l,r)+query(u*2+1,l,r);
}
}
struct BIT{
long long node[N];
void modify(int u,long long x){
for(int i=u;i<=n;i+=lowbit(i)) node[i]+=x;
}
long long query(int u){
long long ans=0;
for(int i=u;i>0;i-=lowbit(i)) ans+=node[i];
return ans;
}
long long query(int l,int r){
return query(r)-query(l-1);
}
}bit1,bit2;
template<typename T>
void read(T& x){
char ch; x=0;
do ch=getchar();
while(ch<'0'||ch>'9');
while(ch>='0'&&ch<='9')
x=x*10+(ch-'0'),ch=getchar();
}
void write(long long x){
char a[24]; int n=0,i;
do a[++n]=x%10+'0',x/=10; while(x>0);
for(i=n;i>0;i--) putchar(a[i]);
putchar('\n');
}
int main(){
// freopen("ds.in","r",stdin);
// freopen("ds.out","w",stdout);
int i,j,s1; read(n),read(q);
for(i=1;i<=n;i++) read(a[i]);
for(i=1;i<=q;i++){
read(qu[i].opt);
if(qu[i].opt==3) read(qu[i].l),read(qu[i].r);
else if(qu[i].opt==1) read(qu[i].x);
}
for(i=1,s1=0;i<=q;i++)
if(qu[i].opt==1) op[++m]={i,s1,qu[i].x};
else if(qu[i].opt==2) s1++;
for(ls.resize(n),i=1;i<=n;i++) ls[i-1]=i;
op[m+1].p=q+1,solve(1,m+1,ls);
for(i=1;i<=n;i++) bit1.modify(i,a[i]);
for(i=1;i<=n;i++) bit2.modify(i,i);
for(SGT::build(1,1,n),s1=0,i=1;i<=q;i++)
switch(qu[i].opt){
case 1:
SGT::modify_chk(1,qu[i].x);
for(j=0;j<chg[i].size();j++){
SGT::modify_act(1,chg[i][j],qu[i].x);
bit1.modify(chg[i][j],-a[chg[i][j]]);
bit2.modify(chg[i][j],-chg[i][j]);
} break;
case 2: SGT::modify_add(),s1++; break;
case 3: write(SGT::query(1,qu[i].l,qu[i].r)+
bit1.query(qu[i].l,qu[i].r)+bit2.query(qu[i].l,qu[i].r)*s1);
}
// fclose(stdin);
// fclose(stdout);
return 0;
}