题解：P6859 蝴蝶与花
Unaccepted_Zhou
·
·
题解
树状树组 + set 短代码。1.4K，写完才知道也不算很短
容易考虑奇偶性。
:::info[分析]
- 如果 s 合法，则 s-2 合法。
- 如果 l 尽量小，r 也尽量小。
- 如果存在 2\space|\space s'([l',r'])-s，r\le r'。
都比较显然。
:::
上述过程大概就是对最大合法的 s 收缩，而且尽量在 r 收缩。
特判 \sum\limits_{i=1}^na_i<s。
考虑先树状树组二分最小的 r'' 使得 \sum\limits_{i=1}^{r''}a_i\ge s。
若不等号取等则 l=1，下文不考虑。
否则，用 set 维护 \{i|a_i=1\}，对 r'' lowerbound() 一下使得 a_{r'-1}=1。
一般情况下：
（$1$）若 $l=1+$`*begin()` 容易求 $r$。
（$2$）否则 $r=r'$，$l\le$`*begin()` 时容易求 $l$，否则不如（$1$）。
特别地，若不存在 $r'$，显然 $l=1+$`*begin()`，然后判断是否合法。
:::success[code]
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=2e6+10;
ll a[N],n,m,x,y,w,c,d; set<ll> s;
void rd(ll &x){
while((d=getchar())<48);
do{x=d-48+x*10;}while((d=getchar())>47);
}
int main(){
rd(n),rd(m);
for(ll i=1;i<=n;i++){
x=0,rd(x),w+=x;
for(ll j=n-i+1;j<=n;j+=j&-j)
a[j]+=x; if(x&1) s.insert(i);//x
}
while(m--){
c=x=y=0,rd(c),rd(x);
if(c=='C'-'0'){
rd(y);
if(y==1&&!s.count(x))//y
s.insert(x),y=-1;
else if(y==2&&s.count(x))
s.erase(x),y=1; else y=0; w+=y;
for(ll j=n-x+1;j<=n;j+=j&-j) a[j]+=y;
}else{
y=0,x=w-x; ll t=0;
if(x==w||x<0){printf("none\n"); continue;}
for(ll j=1<<20;j;j>>=1)
if(y+j<=n&&t+a[y+j]<=x) y+=j,t+=a[y];
y=n-y+1; if(t==x)
{printf("1 %lld\n",y-1); continue;}
auto p=s.upper_bound(y-1);
if(p==s.end()){
p=s.begin();
if(p==s.end()||(*p-1)*2>x)
printf("none\n"); else
printf("%lld %lld\n",*p+1,n-x/2+*p-1);
continue;
}
t-=(*p-y)*2+1,y=*p;
ll f=x-t>>1,g=*s.begin();
if(f<g) printf("%lld %lld\n",f+1,y); else
printf("%lld %lld\n",g+1,y-1-(x-t)/2+g);
}
}
return 0;
}
```
:::
后记：注意输入量！**尤其是 `char` 的输入！**
本题输入 $3\times10^6$ 个 `long long` 和 $10^6$ 个 `char`。
很多人 `cin` `char`，如果习惯 `scanf` 不会关同步流本题极易导致 `TLE`。
而且 `scanf` 占用时间也不少。