T1
对于一次询问 \((x_1,y_1)\) 到 \((x_2,y_2)\),显然若两点不在同一个联通块中则无解。考虑在同一个联通块中的答案。
我们对整张图进行黑白染色。则有结论:若黑色/白色格点存在不同的数,则一定有解。
证明:设此时黑色格点存在两个格点的数互不相同,设这两个格点为 \((a,b)\)、\((c,d)\),我们再寻找一个点 \((x,y)\),满足 \((a,b)\) 可达 \((x,y)\),\((x,y)\) 可达 \((c,d)\)。则我们有这样一条路线:\((x_1,y_1)->...->(a,b)->(x,y)->(c,d)->(x,y)->(a,b)->...->(x,y)->(p,q)->...->(x_2,y_2)\)。考虑这样的路线怎样构造合法解。
对于前半段 \((x_1,y_1)->...->(a,b)\) 和后半段 \((p,q)->...->(x_2,y_2)\),这段的权值是常数,我们不用管。考虑中间一段如何构造。设 \((a,b)\) 的点权为 \(a\),\((c,d)\) 的点权为 \(c\),\((x,y)\) 的点权为 \(b\),则中间的权值可以写成 \(\overline{b?b?b?...?b}\),其中 \(?\) 既可以是 \(a\) 也可以是 \(c\)。
我们先将 \(?\) 全部填成 \(c\),再考虑将 \(c\) 修改成 \(a\) 造成的影响。令路径长为 \(2 \times (P-1) \times (P-1)+1\),则每个 \(?\) 的贡献是 \(a\) 或 \(c\) 的权值 \(\times 100^k\),\(k \in [1,(P-1) \times (P-1)]\)。根据费马小定理我们可以得到 \(100^{P-1} \equiv 1(mod\) \(P)\),而 \(k\) 的取值中满足 \((P-1)|k\) 的 \(k\) 共有 \(P-1\) 种,也就是我们可以依靠这些位将路径的权值加上不超过 \(P-1\) 个 \(a-c\)。由于 \((a-c,P)=1\),所以我们将路径权值加上 \(s\) 个 \(a-c\),\(s \in [0,P-1]\) 可以取遍 \(P\) 的剩余系中所有数,于是路径的权值可以是任何数。
于是对于每次查询,我们只需要判断 \((x_1,y_1)\) 和 \((x_2,y_2)\) 是否在同一个联通块,以及联通块中相同颜色是否存在不同的数即可。
对于不满足条件(同色格的数字都相同)的情况,我们可以预处理出每两种数字对于所有权值是否可达,查询时直接查表即可。这部分的复杂度为 \(O(100P)\)。
对于动态维护联通块信息,我们使用线段树分治 \(+\) 可撤销并查集即可。
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int mod=1145141,N=510,M=250010,T=2e5+10;
int n,m,Q,Id,mp[N][N],lst[N][N],fa[M],siz[M];
int num[2][M],ans[T],vis[N][N],col[M];
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
struct Qry{int st,ed,tar;}q[T];
struct node{int x,y,v;};
vector<node>e[T<<2];
vector<pair<int*,int> >stk;
bool can[10][10][2][mod];
inline int id(int i,int j) {return (i-1)*m+j;}
inline int find(int x) {return x==fa[x]?x:find(fa[x]);}
inline void pb(int &x,int y) {stk.push_back({&x,x});x=y;}
inline void merge(int u,int v) {u=find(u);v=find(v);if(u==v) return ;if(siz[u]>siz[v]) swap(u,v);pb(fa[u],v);pb(siz[v],siz[v]+siz[u]);for(int i=0;i<2;++i) {if(num[i][u]!=-1&&num[i][v]!=-1&&num[i][u]!=num[i][v]) pb(num[i][v],-2);if(num[i][v]==-1&&num[i][u]!=-1) pb(num[i][v],num[i][u]);}
}
inline void back() {while(stk.back().fi!=nullptr) *stk.back().fi=stk.back().se,stk.pop_back();stk.pop_back();
}
#define mid ((l+r)>>1)
#define ls p<<1
#define rs p<<1|1
inline void add(int p,int l,int r,int L,int R,int x,int y,int v) {if(l>R||r<L) return ;if(l>=L&&r<=R) {e[p].push_back((node){x,y,v});return ;}add(ls,l,mid,L,R,x,y,v);add(rs,mid+1,r,L,R,x,y,v);
}
inline void solve(int p,int l,int r) {if(e[p].size()) {stk.push_back({nullptr,0});for(auto [x,y,v]:e[p]) {num[col[id(x,y)]][id(x,y)]=v;pb(vis[x][y],1);for(int i=0;i<4;++i) {int qx=x+dx[i],qy=y+dy[i];if(vis[qx][qy]) merge(id(x,y),id(qx,qy));}}}if(l==r) {if(q[l].st) {int fr=find(q[l].st),to=find(q[l].ed);if(fr!=to) ans[l]=1;else if(num[0][fr]==-2||num[1][fr]==-2) ans[l]=2;else if(num[0][fr]==-1||num[1][fr]==-1) ans[l]=(q[l].tar==num[1][fr]+num[0][fr]+1?2:1);else {int v1=num[col[q[l].st]][fr],v2=num[col[q[l].st]^1][fr];ans[l]=can[v1][v2][col[q[l].st]==col[q[l].ed]][q[l].tar]+1;}}}else solve(ls,l,mid),solve(rs,mid+1,r);if(e[p].size()) back();
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);for(int i=0;i<=9;++i)for(int j=0;j<=9;++j) {int to=0;for(int k=1;;k^=1) {to=(to*10+(k?i:j))%mod;if(can[i][j][k][to]) break;can[i][j][k][to]=1;}}cin>>n>>m>>Q>>Id;for(int i=1;i<=n;++i) {string ch;cin>>ch;for(int j=1;j<=m;++j) mp[i][j]=(ch[j-1]=='#'?-1:ch[j-1]^48),col[id(i,j)]=(i+j)&1,lst[i][j]=1;}for(int i=1;i<=Q;++i) {int opt;cin>>opt;if(opt==1) {int x,y;char c;cin>>x>>y>>c;if(~mp[x][y]) add(1,1,Q,lst[x][y],i-1,x,y,mp[x][y]);lst[x][y]=i;mp[x][y]=c=='#'?-1:(c^48);}else {int x_1,x_2,y_1,y_2,v;cin>>x_1>>y_1>>x_2>>y_2>>v;q[i]=(Qry){id(x_1,y_1),id(x_2,y_2),v};}}for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)if(~mp[i][j]) add(1,1,Q,lst[i][j],Q,i,j,mp[i][j]);for(int i=1;i<=n*m;++i) fa[i]=i,siz[i]=1;memset(num,-1,sizeof(num));solve(1,1,Q);for(int i=1;i<=Q;++i)if(ans[i]) cout<<(ans[i]==2?"Yes":"No")<<'\n';return 0;
}
T4
对于每个 \(c\),我们分开考虑。那么此时使用免费版的人数是固定的,我们只需要考虑使用付费版能获得的最大收益,也就是最大化 \(p \times \sum_{i=1}^n[b_i<c \wedge a_i \ge p]\)。
对于 \(b_i<c\) 的限制,我们对 \(c\) 进行扫描线,每次扫到 \(c+1\) 时加入所有 \(b_i=c\) 的 \(i\),那么此时只剩下 \(a_i \ge p\) 的限制,我们考虑维护每个 \(p\) 的收益 \(v_p\),那么每加入一个 \(i\) 相当于对所有 \(p \in [1,a_i]\) 的 \(v_p\) 加上 \(p\) 的收益,那么此时就变成了:前缀加公差为一等差数列,全局最大值。
这东西一看就很不好用线段树、平衡树之类的数据结构维护,所以我们考虑对序列分块。对于整块,我们打标记。可以发现一个很好的性质:每个点每次进行修改操作时增加的数是一定的。设整块打标记的值为 \(tag\),则一个点的实际值为 \(ans_i=v_i+tag \times i\)。我们将这个式子移项得:\(v_i=-tag \times i +ans_i\)。
设 \(y=v_i\),\(k=-tag\),\(x=i\),\(b=ans_i\),则我们相当于要最大化 \(b\) 的值。这是经典斜率优化板子。我们考虑对每个块维护一个凸包。修改时,整块打标记,散块暴力重构凸包。由于 \(k\) 是单调不增的,所以我们用双端队列维护凸包,查询时不断弹出队头直到队列只剩一个元素或队首与后一个元素的斜率小于 \(k\) 就可以了。
每个元素最多只会进队一次、出队一次,复杂度为 \(O(n \sqrt{n})\)。
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
const int N=1e5+10,B=330;
static char pbuf[1000000],*p1=pbuf,*p2=pbuf;
#define getchar() p1==p2&&(p2=(p1=pbuf)+fread(pbuf,1,1000000,stdin),p1==p2)?EOF:*p1++
inline int read() {int s=0;char ch=getchar();while(ch<'0'||ch>'9') ch=getchar();while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48),ch=getchar();return s;
}
int n,w,bel[N],cnt,mx;
pair<ll,ll>ans;
vector<int>q[N];
struct block{int L,R,det,d[B];ll a[B],tag;inline double slope(int i,int j) {return 1.0*(a[i]-a[j])/(i-j);}inline void rebuild() {L=0,R=-1;for(int i=0;i<B;++i) {while(R>L&&slope(i,d[R])>=slope(d[R],d[R-1])) R--;d[++R]=i;}}inline pair<ll,ll> add(int k) {if(k==B) tag++;else {for(int i=0;i<k;++i) a[i]+=det+i;for(int i=0;i<B;++i) a[i]+=tag*(det+i);tag=0;rebuild();}while(L<R&&a[d[L]]+tag*d[L]<=a[d[L+1]]+tag*d[L+1]) L++;return make_pair(a[d[L]]+tag*(det+d[L]),det+d[L]);}
}b[B];
signed main() {cnt=n=read(),w=read();for(int i=0;i<N;++i) bel[i]=i/B;for(int i=0;i<B;++i) b[i].d[0]=B-1,b[i].det=i*B;for(int i=1,a,b;i<=n;++i) {a=read(),b=read();q[b].push_back(a);mx=max(mx,b);}for(int i=0;i<=mx+1;++i) {printf("%lld %lld\n",ans.fi+1ll*cnt*i*w,ans.se);for(auto v:q[i]) {int pos=bel[v];cnt--;for(int i=0;i<pos;++i) ans=max(ans,b[i].add(B));ans=max(ans,b[pos].add(v-pos*B+1));}}return 0;
}