题目
题目链接：https://www.luogu.com.cn/problem/P6859
Amazing John 很喜欢花。
Amazing John 的花圃里有 \(n\) 朵花，他每天都会在花园里散步。
对于每一朵花 Amazing John 会评价它好看或不好看。被评价好看的花的美丽值为 \(2\)，被评价不好看的花的美丽值为 \(1\)。
我们可以抽象的把这 \(n\) 朵花看做在一条直线上。每次散步时， Amazing John 会从任意一朵花开始，一直往下一朵花走。到任意一朵花结束。在路途中，他会将所有经过的花的美丽值统计下来。（当然包括开始的花和结束的花）
现在 Amazing John 想知道，能否有一种散步方案，使得他从第 \(l\) 朵花走到第 \(r\) 朵花的美丽值之和正好是 \(s\)？
为了少走一些路， Amazing John 要你给出在所有方案中 \(l\) 最小的方案。
当然，为了避免在花圃中散步过于单调， Amazing John 随时可能会将一朵花的美丽值更改。
每个询问之间互相独立，即统计过的花朵在下次询问时仍可被统计。
算法 1
枚举左端点，发现在左端点不断向右扫描的过程中，右端点的位置也一定单调不减。所以不用每次重新开始扫描右端点，在上一次扫描的基础上继续向右即可。
时间复杂度 \(O(nm)\)，期望得分 \(20pts\)。
算法 2
将原序列做前缀和，设做前缀和后的序列为 \(s\)，问题转化为求最小的两个位置 \(i,j\) 使得 \(s_j-s_i=k\)。
对于修改操作，相当于将序列 \(s\) 的一段后缀全部加上一个数；对于查询操作，可以枚举左端点，二分出右端点，如果这一段区间的和为 \(k\) 即为答案。
时间复杂度 \(O(nm\log n)\) 或 \(O(nm\log^2 n)\)，取决于是在数据结构内二分还是二分套数据结构。写的好看一些或许可以拿到 \(20pts\)。
甚至没有算法 1 优秀。
算法 3
在算法 2 中，容易发现我们二分出的每一段区间和要么是 \(k\)，要么是 \(k+1\)。因为如果和大于 \(k+1\) 的话，右端点向左移动一位和肯定不小于 \(k\)。
假设我们二分出的两个区间为 \([l,r_1]\) 和 \([l+1,r_2]\)，且这两个区间的和均为 \(k+1\)，那么：
-
\(a_l\) 一定等于 \(2\)，否则 \([l+1,r_1]\) 就是一个合法的和为 \(k\) 的区间。
-
\(a_{r_1}\) 一定等于 \(2\)，否则 \([l,r_1-1]\) 就是一个合法的和为 \(k\) 的区间。
-
\(r_2=r_1+1\)，因为 \(\sum^{r_1}_{i=l} a_i=\sum^{r_2}_{i=l+1}a_i-\sum^{r_2}_{i=r_1+1}a_i+a_l\)，而 \(a_l=2\)，当 \(r_2>r_1+1\) 时， \(\sum^{r_2}_{i=r_1+1}a_i=2\) 当且仅当 \(r_2=r_1+2\) 且 \(a_{r_1+1}=a_{r_1+2}=1\)，此时区间 \([l,r_1+1]\) 就是一个合法的和为 \(k\) 的区间。
最后一点换句话说，黄色部分的和一定等于蓝色部分的和，而蓝色部分的和为 \(2\)，那么只有当 \(r_2=r_1+1\) 且 \(a_{r_2}=2\) 时才满足条件。
那如果再加入一个区间 \([l+2,r_3]\)，那么就有 \(a_{l+1}=a_{r2}=2,r_3=r_2+1\)。我们发现，只要接下来有一个位置不是 \(2\) 了，那么一定存在一个和为 \(k+1\) 的区间，也就是答案区间与连续的 \(2\) 的个数有关。
那么我们用数据结构维护前缀和，对于每一次询问，二分出从位置 \(1\) 开始和不小于 \(k\) 的区间 \([1,p]\)。然后再用数据结构求出位置 \(1\) 和位置 \(p\) 后连续的 \(2\) 的个数，假设分别为 \(cnt1\) 个和 \(cnt2\) 个，
-
当 \(cnt1<cnt2\) 时，区间 \([2+cnt1,p+cnt1]\) 即为答案。
-
当 \(cnt1\geq cnt2\) 时，区间 \([1+cnt2,p+cnt2]\) 即为答案。
可以手写小数据来理解。
那么我们需要解决两个问题：
-
如何找到第一个前缀和不小于 \(k\) 的位置。
-
如何求出一个位置后面有多少个连续的 \(2\)。
对于问题 1，直接采用二分+数据结构即可。对于问题 2，依然可以二分长度，假设为 \(len\)，那么只需要判断区间 \([p,p+len-1]\) 的和是否为 \(2\times len\) 即可。
采用树状数组或者线段树实现均可。
时间复杂度 \(O(m\log^2 n)\)，期望得分 \(50pts\)。
算法 4
可以在算法 3 的基础上，在数据结构内二分。可以省掉一个 \(\log\)。
树状数组二分或线段树二分均可，后者写法不优美可能会被卡。
时间复杂度 \(O(m\log n)\)，期望得分 \(100pts\)。
代码
#include <bits/stdc++.h>
using namespace std;
const int N=(2<<21)+10,LG=20,Inf=1e9;
int n,m,a[N];
char ch;
inline int read()
{
int d=0; char ch=getchar();
while (!isdigit(ch)) ch=getchar();
while (isdigit(ch)) d=(d<<3)+(d<<1)+ch-48,ch=getchar();
return d;
}
void write(int x)
{
if (x>9) write(x/10);
putchar(x%10+48);
}
inline void print(int x,int y)
{
write(x); putchar(32);
write(y); putchar(10);
}
struct BIT
{
int c[N];
inline void add(int x,int v)
{
for (int i=x;i<N;i+=i&-i)
c[i]+=v;
}
inline int query(int x)
{
int ans=0;
for (int i=x;i;i-=i&-i)
ans+=c[i];
return ans;
}
inline int query1(int k)
{
int p=0,sum=0;
for (int i=LG;i>=0;i--)
{
int s=(1<<i);
if (sum+c[p+s]<=k) p+=s,sum+=c[p];
}
return p;
}
inline int query2(int k)
{
int p=0,sum=0,pres=query(k-1);
for (int i=LG;i>=0;i--)
{
int s=(1<<i);
if (sum+c[p+s]-pres==(p+s-k+1)*2 || p+s<k)
p+=s,sum+=c[p];
}
return p;
}
}bit;
int main()
{
n=read(); m=read();
for (int i=1;i<=n;i++)
{
a[i]=read();
bit.add(i,a[i]);
}
bit.add(n+1,Inf);
while (m--)
{
while (ch=getchar())
if (ch=='C' || ch=='A') break;
if (ch=='C')
{
int x=read(),y=read();
bit.add(x,y-a[x]);
a[x]=y;
}
else
{
int x=read(),pos=bit.query1(x);
if (!x || x>bit.query(n)) puts("none");
else if (bit.query(pos)==x) printf("1 %d\n",pos);
else
{
pos++;
int len1=bit.query2(1),len2=bit.query2(pos)-pos+1;
if (len1<len2)
{
if (pos+len1<=n) print(2+len1,pos+len1);
else puts("none");
}
else
{
if (pos+len2<=n) print(1+len2,pos+len2);
else puts("none");
}
}
}
}
return 0;
}