P2496 [SDOI2012] 体育课题意给出一个数组请支持一下三种操作1.L R\verb!1.L R!1.L R查询区间[L,R][L,R][L,R]中的最大值2.L R\verb!2.L R!2.L R交换LLL,RRR的值3.L R T\verb!3.L R T!3.L R T对∀i∈[l,r]\forall i\in[l,r]∀i∈[l,r]其值增加(i−L1)×T(i-L1)\times T(i−L1)×T其中1≤n,m≤1051 \le n,m \le 10^51≤n,m≤1050≤t≤1040 \le t \le 10^40≤t≤1041≤ai≤1081 \leq a_i \leq 10^81≤ai​≤108赛时思路 以及 题解假如没有二操作那么总体最大值一定不断右移那么分块对每个快内维护最大值时间复杂度为O(mn)O(m\sqrt n)O(mn​)瓶颈在于查询现加上二操作那么可以将a,ba,ba,b所涉及的两个块直接暴力重构块内维护的复杂度为O(nmn)O(nm\sqrt n)O(nmn​)所以每个块内维护一个下凸包交换时暴力重构即可总结切入点在于最大值不断右移然后再从具体的题目操作想到分块后面的维护思路便是自然而然的了代码#includebits/stdc.h # define Maxn 100005 # define ll long long using namespace std; int n,m,SZ; ll a[Maxn],t; int L[Maxn],R[Maxn],blo[Maxn]; int type,l,r; void Rec(int x); void Init() { SZsqrt(n); if(SZ0) SZ1; int cnt0; for(int i1;in;i) { if((i-1)%SZ0) { cnt; L[cnt]i; } blo[i]cnt; R[cnt]i; } } ll K[Maxn],B[Maxn]; int pos[Maxn],ed[Maxn]; vectorint s[Maxn]; ll CalcVal(int x,int y) {return a[x]1ll*x*K[y]-B[y];} void Rec(int x) { s[x].clear(),ed[x]0; for(int iL[x];iR[x];i) { while(ed[x]2) { int lsts[x][ed[x]-1],lstts[x][ed[x]-2]; if(1ll*(a[i]-a[lst])*(lst-lstt)1ll*(a[lst]-a[lstt])*(i-lst)) ed[x]--,s[x].pop_back(); else break; } ed[x],s[x].push_back(i); } pos[x]0; while(pos[x]ed[x]-1) { if(CalcVal(s[x][pos[x]],x)CalcVal(s[x][pos[x]1],x)) pos[x]; else break; } } void Down(int x) { for(int iL[x];iR[x];i) a[i]1ll*i*K[x]-B[x]; K[x]B[x]0; Rec(x); } ll Ask_Max(int l,int r) { if(blo[l]blo[r]) { ll res0; for(int il;ir;i) resmax(res,CalcVal(i,blo[l])); return res; } ll resmax(Ask_Max(l,R[blo[l]]),Ask_Max(L[blo[r]],r)); for(int iblo[l]1;iblo[r];i) resmax(res,CalcVal(s[i][pos[i]],i)); return res; } void Modify(int l,int r,ll k) { if(blo[l]blo[r]) { Down(blo[l]); for(int il;ir;i) a[i]1ll*(i-l1)*k; Rec(blo[l]); return ; } Down(blo[l]); for(int il;iR[blo[l]];i) a[i]1ll*(i-l1)*k; Rec(blo[l]); Down(blo[r]); for(int iL[blo[r]];ir;i) a[i]1ll*(i-l1)*k; Rec(blo[r]); for(int iblo[l]1;iblo[r];i) { K[i]k,B[i]1ll*(l-1)*k; while(pos[i]ed[i]-1) { if(CalcVal(s[i][pos[i]],i)CalcVal(s[i][pos[i]1],i)) pos[i]; else break; } } } int main() { scanf(%d%d,n,m),Init(); for(int i1;in;i) scanf(%lld,a[i]); for(int i1;iblo[n];i) Rec(i); while(m--) { scanf(%d,type); if(type1) { scanf(%d%d,l,r); ll v1Ask_Max(1,1),v2Ask_Max(l,r); printf(%lld\n,max(0ll,v2-v1)); } if(type2) { scanf(%d%d,l,r); Down(blo[l]); if(blo[l]!blo[r]) Down(blo[r]); swap(a[l],a[r]),Rec(blo[l]); if(blo[l]!blo[r]) Rec(blo[r]); } if(type3) { scanf(%d%d%lld,l,r,t); Modify(l,r,t); } // for(int i1;in;i) printf(%lld ,Ask_Max(i,i));printf(\n); } return 0; }//P3713 [BJOI2017] 机动训练题意定义机动路径为始终向同一象限方向移动的路径其权值定义顺序经过的字母所连成的字符串令CntSCnt_SCntS​为权值为SSS的机动路径的条数求∑SCntS2\sum_S Cnt_S^2∑S​CntS2​其中1≤m,n≤301 \le m, n \le 301≤m,n≤30字符集由大小写字母数字和.*构成题解∑SCntS2\sum_S Cnt_S^2S∑​CntS2​∑S∑i1CntS∑i1CntS1\sum_S \sum_{i1}^{Cnt_S}\sum_{i1}^{Cnt_S}1S∑​i1∑CntS​​i1∑CntS​​1所以答案可以看作每次同时走两条路径求使它们权值相等的方案数容易想到每次钦定方向以及起点随后跑记忆化搜索但有一个小问题就是直线可能会算重容斥一下即可代码#includebits/stdc.h # define Maxn 35 # define pr pairint,int # define fir first # define sec second # define mod 1000000009 using namespace std; bool vis[Maxn][Maxn][Maxn][Maxn]; int n,m; int f[Maxn][Maxn][Maxn][Maxn],ans; int cnt1,cnt2; pr F1[10],F2[10]; char a[Maxn][Maxn]; int dfs(int x,int y,int sx,int sy) { if(vis[x][y][sx][sy]) return f[x][y][sx][sy]; vis[x][y][sx][sy]1; f[x][y][sx][sy]1; for(int i1;icnt1;i) { for(int j1;jcnt2;j) { int xxxF1[i].fir,yyyF1[i].sec; int sx1sxF2[j].fir,sy1syF2[j].sec; if(xx1xxnyy1yymsx11sx1nsy11sy1ma[xx][yy]a[sx1][sy1]) f[x][y][sx][sy](f[x][y][sx][sy]dfs(xx,yy,sx1,sy1))%mod; } } return f[x][y][sx][sy]; } void Write1(int x) { if(x0) { cnt13; F1[1]{1,0}; F1[2]{1,-1}; F1[3]{0,-1}; } if(x1) { cnt13; F1[1]{-1,0}; F1[2]{-1,-1}; F1[3]{0,-1}; } if(x2) { cnt13; F1[1]{-1,0}; F1[2]{-1,1}; F1[3]{0,1}; } if(x3) { cnt13; F1[1]{1,0}; F1[2]{1,1}; F1[3]{0,1}; } if(x4) { cnt11; F1[1]{1,0}; } if(x5) { cnt11; F1[1]{0,-1}; } if(x6) { cnt11; F1[1]{-1,0}; } if(x7) { cnt11; F1[1]{0,1}; } } void Write2(int x) { if(x0) { cnt23; F2[1]{1,0}; F2[2]{1,-1}; F2[3]{0,-1}; } if(x1) { cnt23; F2[1]{-1,0}; F2[2]{-1,-1}; F2[3]{0,-1}; } if(x2) { cnt23; F2[1]{-1,0}; F2[2]{-1,1}; F2[3]{0,1}; } if(x3) { cnt23; F2[1]{1,0}; F2[2]{1,1}; F2[3]{0,1}; } if(x4) { cnt21; F2[1]{1,0}; } if(x5) { cnt21; F2[1]{0,-1}; } if(x6) { cnt21; F2[1]{-1,0}; } if(x7) { cnt21; F2[1]{0,1}; } } signed main() { scanf(%d%d,n,m); for(int i1;in;i) { for(int j1;jm;j) cina[i][j]; } // printf(%d\n,ans); for(int fx0;fx4;fx) { for(int fy0;fy4;fy) { Write1(fx4),Write2(fy); memset(vis,0,sizeof(vis)),memset(f,0,sizeof(f)); for(int x1;xn;x) { for(int y1;ym;y) { for(int sx1;sxn;sx) { for(int sy1;sym;sy) { if(a[x][y]!a[sx][sy]) continue; ans(ans-dfs(x,y,sx,sy)mod)%mod; } } } } Write1(fx),Write2(fy4); memset(vis,0,sizeof(vis)),memset(f,0,sizeof(f)); for(int x1;xn;x) { for(int y1;ym;y) { for(int sx1;sxn;sx) { for(int sy1;sym;sy) { if(a[x][y]!a[sx][sy]) continue; ans(ans-dfs(x,y,sx,sy)mod)%mod; } } } } Write1(fx4),Write2(fy4); memset(vis,0,sizeof(vis)),memset(f,0,sizeof(f)); for(int x1;xn;x) { for(int y1;ym;y) { for(int sx1;sxn;sx) { for(int sy1;sym;sy) { if(a[x][y]!a[sx][sy]) continue; ans(ansdfs(x,y,sx,sy))%mod; } } } } Write1(fx),Write2(fy); memset(vis,0,sizeof(vis)),memset(f,0,sizeof(f)); for(int x1;xn;x) { for(int y1;ym;y) { for(int sx1;sxn;sx) { for(int sy1;sym;sy) { if(a[x][y]!a[sx][sy]) continue; ans(ansdfs(x,y,sx,sy))%mod; } } } } } } printf(%d\n,ans); return 0; }P4563 [JXOI2018] 守卫题意有nnn个亭子第iii个的坐标为(i,hi)(i,h_i)(i,hi​)定义亭iii能看到亭jjj当且仅当i≤ji \leq ji≤j且i,ji,ji,j的连线上方没有任何亭子对于每个区间[l,r][l,r][l,r]求一个亭子集合E⊆[l,r]E \subseteq [l,r]E⊆[l,r]s.t.s.t.s.t.[l,r][l,r][l,r]中每个亭都能被至少一个EEE中的亭看到其中n≤5000n\leq 5000n≤50001≤hi≤1091\leq h_i\leq 10^91≤hi​≤109赛时思路不妨先将任意两个亭子间能否相互看到预处理出来观察到任一保安的监视范围为一个区间于是问题转化为对于每个区间[l,r][l,r][l,r]找到一个下标均在[l,r][l,r][l,r]的区间集合s.t.s.t.s.t.集合的交包含[l,r][l,r][l,r]我们考虑将lll固定rrr不断移动的情形设现在要从[l,r−1][l,r-1][l,r−1]扩展至[l,r][l,r][l,r]第111种情况原集合不动只考虑rrr的放置第222种情况原集合变动我们考虑rrr能替换掉原集合中的什么点思考iii能跨过jjj监视kkk的条件是什么不难想到是Ri,jRj,kR_{i,j}R_{j,k}Ri,j​Rj,k​其中Ra,bR_{a,b}Ra,b​表示a,ba,ba,b两点间的斜率那么此时jjj的功能可以被iii或kkk完美替代更进一步的对于一个下凸包而言易证一种任何两点都能相互监视所以整个下凸包的功能能被最左端和最右端替代于是我们删图中的下凸包即维护一个上凸包此时因为上凸包上任意点能且仅能监视它的相邻节点所以anslen2ans\frac{len}{2}ans2len​其中lenlenlen为上凸包的大小再重新套用回上面将lll固定的思路发现我们要做的只有不断在图中加点并维护上凸包这个用一个单调栈显然是好维护的时间复杂度O(n2)O(n^2)O(n2)题解赛时实际上看错了题没有看到下标也有大小限制所以赛时思路里有很多错误的结论但我认为思路里对于凸包的思考应该是一个比较自然的想法但顺着想下去并不能发现太好的性质于是我们可以转换一下思路注意到若[l,r][l,r][l,r]满足条件那么rrr必须选选完后发现剩下了许多空段而这些空段间不能证明是不会互相影响的所以设fl,rf_{l,r}fl,r​为 区间[l,r][l,r][l,r]的答案转移根据以上所讲是容易的代码#includebits/stdc.h # define Maxn 5005 # define db double using namespace std; bool bz[Maxn][Maxn]; int n,a[Maxn]; int s[Maxn],top; int f[Maxn][Maxn],g[Maxn][Maxn]; int ans,now; bool Ask(int l,int p,int r) { if(pr) return 1; return 1ll*(a[r]-a[p])*(p-l)1ll*(a[p]-a[l])*(r-p); } int main() { scanf(%d,n); for(int i1;in;i) scanf(%d,a[i]); // printf(%d\n,bz[1][2]); for(int r1;rn;r) { f[r][r]1,ans^1; int posr; for(int lr-1;l1;l--) { f[l][r]2e91; if(Ask(l,pos,r)) posl; f[l][r]min(f[l][r],min(f[l][pos],f[l][pos-1])f[pos1][r]); ans^f[l][r]; // printf(%d %d: %d\n,l,r,f[l][r]); } } printf(%d\n,ans); return 0; }