A. 序列

发现较难维护的是后一个信息。

所以考虑直接分块维护。

为每个块开一个vector，表示这个块中所有元素对vector中的所有元素依次取过max。

因为取max的性质，这个vector中的元素只需要保留单调递增的部分。

在查询的时候和暴力重构一些块的时候，可以直接在vector中二分确定某个元素更新了多少次。

因为卡内存，所以每隔5000次询问暴力重构所有块一次。

询问时手贱把upperbound打成lowerbound，哭了。

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 const int N=1e5+7;
 5 int n,m,sq;
 6 ll a[N],add[700];
 7 int sz[N],bl[N],tim[700];
 8 vector<ll> ve[700];
 9 inline void rebuild(int k){
10     if(!tim[k]&&ve[k].empty()) return ; 
11     int l=(k-1)*sq+1,r=min(n,k*sq);
12     for(int i=l;i<=r;++i){
13         sz[i]+=ve[k].end()-upper_bound(ve[k].begin(),ve[k].end(),a[i])+tim[k];
14         if(!ve[k].empty()) a[i]=max(a[i],ve[k].back())+add[k];
15         else a[i]+=add[k];
16     }
17     tim[k]=0; add[k]=0; ve[k].clear();
18 }
19 inline void modify(int l,int r,int c){
20     if(!c) return ;
21     rebuild(bl[l]); rebuild(bl[r]);
22     for(int i=l,lim=min(bl[l]*sq,r);i<=lim;++i) ++sz[i],a[i]+=c;
23     if(bl[l]!=bl[r]) for(int i=(bl[r]-1)*sq+1;i<=r;++i) ++sz[i],a[i]+=c;
24     for(int i=bl[l]+1;i<bl[r];++i) add[i]+=c,++tim[i];
25 }
26 inline void insert(int l,int r,int c){
27     rebuild(bl[l]); rebuild(bl[r]);
28     for(int i=l,lim=min(bl[l]*sq,r);i<=lim;++i) if(c>a[i]) a[i]=c,++sz[i];
29     if(bl[l]!=bl[r]) for(int i=(bl[r]-1)*sq+1;i<=r;++i) if(c>a[i]) a[i]=c,++sz[i];
30     for(int i=bl[l]+1;i<bl[r];++i) if(ve[i].empty()||c-add[i]>ve[i].back()) ve[i].push_back(c-add[i]);
31 }
32 inline void query(int x){
33     int k=bl[x];
34     if(!ve[k].empty()) printf("%lld ",max(a[x],ve[k].back())+add[k]);
35     else printf("%lld ",a[x]+add[k]);
36     printf("%d\n",sz[x]+ve[k].end()-upper_bound(ve[k].begin(),ve[k].end(),a[x])+tim[k]);
37 }
38 inline int read(register int x=0,register char ch=getchar(),register int f=0){
39     for(;!isdigit(ch);ch=getchar()) f=ch=='-';
40     for(; isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
41     return f?-x:x;
42 }
43 int main(){
44     n=read(); sq=sqrt(n)*0.5+1;
45     for(int i=1;i<=n;++i) a[i]=read(),bl[i]=(i-1)/sq+1;
46     m=read();
47     for(int i=1,l,r,c;i<=m;++i){
48         char ch=getchar(); while(!isalpha(ch)) ch=getchar();
49         if(ch=='A') l=read(),r=read(),c=read(),modify(l,r,c);
50         else if(ch=='M') l=read(),r=read(),c=read(),insert(l,r,c);
51         else query(read());
52         if(!(i&4095)) for(int j=1;j<=bl[n];++j) rebuild(j);
53     }
54     return 0;
55 }
分块

复杂度瓶颈在于修改时的暴力重构，复杂度为$O(n \sqrt{nlogn})$。

发现在重构时可以通过单调指针，所以维护每个块中元素的大小顺序，对于修改操作可以进行二路归并，总复杂度$O(n\sqrt n)$。

正解做法是离线后进行扫描线操作。

将每个操作视为在左端点加入，右端点删除。

容易发现可以把相邻的加法操作合在一起，于是操作序列转化为$A_1\ M_1\ A_2\ M_2\ A_3\ M_3$的形式。

考虑已经维护了原来的合法的取max操作，设$s_i$表示$A_i$的前缀和。

取max操作能够成立仅当$M_{i-1}+s_i-s_{i-1}<M_i$。

移项可得$M_{i-1}-s_{i-1}<M_i-s_{i}$，所以只要维护$M_i-s_i$形成的单调递增的结构就可以了。

这个东西可以用线段树维护单调栈的思路维护。

 

B. 旅行计划

部分分很简单，但是正解很难想到。

正解大概是取$d$为$k$和联通块内所有边权的gcd。

答案显然只能为$d$的倍数，不妨将所有的边权和$k$都除掉$d$。

存在一种情况，使得联通块内所有边权在模$k$意义下总和为$1$。

然而只可以简单地构造一条回路，使得经过联通块内任意边任意偶数次（题解给出的构造方法是在DFS树上走，遇到非树边可以来回转）。

所以构造出一条在模$k$意义下贡献为$2$的回路$C$是可行的。

如果$k$为奇数，那么一定可以通过不断走$u\rightarrow v\rightarrow u$这条路径，使得最终答案为$0$。

只需要考虑$k$为偶数。

现在考虑$u\ v$之间是否存在一条长度为偶数（即在模$2$意义下为$0$）的路径。

因为已经有了回路$C$，如果存在长度为偶数的路径，答案一定为$0$。

如果不存在，那么答案只能为$1$。

所以对于每个联通块分别奇偶染色（当然这里的染色标准并不是相邻异色），判是否为二分图就可以了。

然而还有一个问题是，每次给出的$k$是不同的，所以没有办法预处理。

然而注意到这里的$k$在除过$d$之后仍为偶数，也就是说$k$中质因子$2$的个数要比原联通块的$gcd$中$2$的个数要多。

所以原联通块中边权在除两个不同的$gcd$之后的奇偶性是相同的，所以直接预处理是可行的。

 

C. Hack

可以发现直接用最小割就可以保证每条路径一定被割，但是却不能保证只割一次。

手玩发现割不止一次的情况，等价于源点汇点分别形成的$S$/$T$集合中，满足$T$集合内存在边回到$S$集合，然后就死掉了。

题解给出的做法是，对每条边建立边权为$inf$的反向边，这样上述的情况会存在增广路，所以上述情况并不是一个合法的割。

所以直接跑最小割就可以了。