sol 61003线段树签到题注意到最多排2次如果出现 2 1 0则一定需要排2次如果已经有序则无需排序其余情况一次线段树维护 2 1 0 的出现情况#includebits/stdc.h#define int long long#define inf 0x3f3f3f3f3f3f3f#define GG ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#define cnot coutNO\n#define cyes coutYES\n#define cans coutans\n#define pb push_back#define x0 first#define y0 second#define lc p1#define rc p1|1#define mem(a,b) memset(a,b,sizeof(a))#define sp(x) fixedsetprecision(x)#define all(v) v.begin(),v.end()#define fr(i,st,ed) for(int ist;ied;i)#define ffr(i,st,ed,dt) for(int ist;ied;idt)using namespace std;typedef pairint,stringPis;typedef pairint,intPii;typedef pairstring,stringPss;const int N2e510,mod1e97,M1e610;int lowbit(int x){return x(-x);}struct Node{bool f;int l,r;bool h0,h1,h2,h10,h21,h210;};Node tree[N2];int a[N];void up(int p){tree[p].f(tree[lc].ftree[rc].ftree[lc].rtree[rc].l);tree[p].ltree[lc].l;tree[p].rtree[rc].r;tree[p].h0tree[lc].h0||tree[rc].h0;tree[p].h1tree[lc].h1||tree[rc].h1;tree[p].h2tree[lc].h2||tree[rc].h2;tree[p].h10(tree[lc].h10||tree[rc].h10)||(tree[lc].h1tree[rc].h0);tree[p].h21(tree[lc].h21||tree[rc].h21)||(tree[lc].h2tree[rc].h1);tree[p].h210(tree[lc].h210||tree[rc].h210)||(tree[lc].h2tree[rc].h10)||(tree[lc].h21tree[rc].h0);}void build(int p,int l,int r){if(lr){tree[p].ftrue;tree[p].ltree[p].ra[l];tree[p].h0(a[l]0);tree[p].h1(a[l]1);tree[p].h2(a[l]2);tree[p].h10false;tree[p].h21false;tree[p].h210false;return;}int mid(lr)1;build(lc,l,mid);build(rc,mid1,r);up(p);}void upd(int p,int l,int r,int pos,int val){if(lr){tree[p].ltree[p].rval;tree[p].h0(val0);tree[p].h1(val1);tree[p].h2(val2);tree[p].h10false;tree[p].h21false;tree[p].h210false;return;}int mid(lr)1;if(posmid)upd(lc,l,mid,pos,val);else upd(rc,mid1,r,pos,val);up(p);}Node que(int p,int l,int r,int ql,int qr){if(qllrqr){return tree[p];}int mid(lr)1;if(qrmid)return que(lc,l,mid,ql,qr);else if(qlmid)return que(rc,mid1,r,ql,qr);else{Node reslque(lc,l,mid,ql,qr);Node resrque(rc,mid1,r,ql,qr);Node res;res.fresl.fresr.f(resl.rresr.l);res.lresl.l;res.rresr.r;res.h0resl.h0||resr.h0;res.h1resl.h1||resr.h1;res.h2resl.h2||resr.h2;res.h10(resl.h10||resr.h10)||(resl.h1resr.h0);res.h21(resl.h21||resr.h21)||(resl.h2resr.h1);res.h210(resl.h210||resr.h210)||(resl.h2resr.h10)||(resl.h21resr.h0);return res;}}void init(){mem(tree,0);mem(a,0);}void solve(){int n,q;cinnq;init();fr(i,1,n){cina[i];}build(1,1,n);while(q--){int op;cinop;if(op1){int p,x;cinpx;upd(1,1,n,p,x);}else{int l,r;cinlr;Node resque(1,1,n,l,r);if(res.f)cout0\n;else if(!res.h210)cout1\n;else cout2\n;}}}signed main(){GG;int _t1;cin_t;while(_t--){solve();}}1005学过AVL的看这个应该很好理解中序遍历就是原数组的顺序也就是询问等价 两个节点的lca为根左边的部分后缀子树和右边的部分前缀子树的最大深度首先AVL建树然后类似bfs求深度/高度树上st表求lca考虑如何求前缀/后缀子树的深度以前缀举例我们先考虑一个节点往父亲节点跳的过程--如果该节点对于父亲而言是左节点那么它不在被范围包裹的前缀无需考虑如果是右节点那么它贡献的方式是 当前子树的值 与 它父亲节点左子树的值 取max,显式表示f(x)max(1h[lc(p)],x1)对于每一个这样的操作都可以抽象成f(x)max(a,xb)考虑多个函数的复合设f(x)max⁡(a,xb)g(x)max(c,xd)先应用 g再应用 ff(g(x))max⁡(a,g(x)b)max⁡(a,max⁡(c,xd)b)max⁡(a,cb,xdb)所以组合后仍然是同样形式f∘g(x)max⁡(max⁡(a,cb),x(bd))也就是代码的meg部分这部分操作同样可以在st建表过程一并完成后缀取反同理查询给出底部节点的x查询路径考虑左/右取max即可#includebits/stdc.h#define int long long#define inf 0x3f3f3f3f3f3f3f#define GG ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#define cnot coutNO\n#define cyes coutYES\n#define cans coutans\n#define pb push_back#define x0 first#define y0 second//#define lc p1//#define rc p1|1#define mem(a,b) memset(a,b,sizeof(a))#define sp(x) fixedsetprecision(x)#define all(v) v.begin(),v.end()#define fr(i,st,ed) for(int ist;ied;i)#define ffr(i,st,ed,dt) for(int ist;ied;idt)using namespace std;typedef pairint,stringPis;typedef pairint,intPii;typedef pairstring,stringPss;const int N20,mod1e97,M1e610;int lowbit(int x){return x(-x);}struct Fn{int a,b;};Fn meg(Fn f,Fn g){return {max(f.a,g.af.b),f.bg.b};}int calc(Fn f,int x){return max(f.a,xf.b);}void solve(){int n,q;cinnq;vectorinta(n1),lc(n1),rc(n1),fa(n1),stk;fr(i,1,n){cina[i];int lst0;while(!stk.empty()a[stk.back()]a[i]){lststk.back();stk.pop_back();}if(!stk.empty()){rc[stk.back()]i;fa[i]stk.back();}if(lst){lc[i]lst;fa[lst]i;}stk.pb(i);}int rtstk[0];vectorintdep(n1),h(n1),ord;stk{rt};while(!stk.empty()){int ustk.back();stk.pop_back();ord.pb(u);if(lc[u]){dep[lc[u]]dep[u]1;stk.pb(lc[u]);}if(rc[u]){dep[rc[u]]dep[u]1;stk.pb(rc[u]);}}reverse(all(ord));for(int u:ord)h[u]1max(h[lc[u]],h[rc[u]]);const Fn INF{-inf,0};arrayvectorint, N up;arrayvectorFn, N pre, suf;fr(j, 0, N - 1) {up[j].resize(n 1);pre[j].assign(n 1, INF);suf[j].assign(n 1, INF);}fr(u,1,n){if(urt){up[0][u]u;continue;}int pfa[u];up[0][u]p;if(rc[p]u)pre[0][u]{1h[lc[p]],1};if(lc[p]u)suf[0][u]{1h[rc[p]],1};}fr(j,1,N-1){fr(u,1,n){int pup[j-1][u];up[j][u]up[j-1][p];pre[j][u]meg(pre[j-1][p],pre[j-1][u]);suf[j][u]meg(suf[j-1][p],suf[j-1][u]);}}auto lca[](int u,int v){if(dep[u]dep[v])swap(u,v);int ddep[u]-dep[v];fr(j,0,N-1){if((dj)1)uup[j][u];}if(uv)return u;for(int jN-1;j0;j--){if(up[j][u]!up[j][v]){uup[j][u];vup[j][v];}}return fa[u];};auto path[](int u,int v,const autof){Fn resINF;int ddep[v]-dep[u];fr(j,0,N-1){if((dj)1){resmeg(f[j][v],res);vup[j][v];}}return res;};auto pref[](int u,int v){return calc(path(u,v,pre),1h[lc[v]]);};auto suff[](int u,int v){return calc(path(u,v,suf),1h[rc[v]]);};while(q--){int l,r;cinlr;int mlca(l,r);int Llm?suff(lc[m],l):0;int Rmr?pref(rc[m],r):0;cout1max(L,R)\n;}}signed main(){GG;int _t1;cin_t;while(_t--){solve();}}10061-n内的每一个数一定要出现1次反向思考在1-n成排列时最后一个数必然为n个数的中位数我们反向模拟删数的过程具体的对于每一个中位数我们考虑它作为中位数需要在原数组中满足的条件即删除两个数如果当前的数的个数-11,说明它仍然需要在b数组出现也就是需要作为中位数不能删维护 还未考虑的数 和 可以被删除的数对于一个中位数p如果它的出现次数-11,说明它还需要作为中位数此时删除它的两边如果0说明它不需要被作为中位数了分别考虑中位数左移/右移左移需要删除p和nxt[p](在可删除数组中右移反之分别考虑可行性由此引出一个必要性判断每[p-d,pd]需要承担d的中位数在rem余量数组先行判断#includebits/stdc.h#define int long long#define inf 0x3f3f3f3f3f3f3f#define GG ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#define cnot coutNO\n#define cyes coutYES\n#define cans coutans\n#define pb push_back#define x0 first#define y0 second#define lc p1#define rc p1|1#define mem(a,b) memset(a,b,sizeof(a))#define sp(x) fixedsetprecision(x)#define all(v) v.begin(),v.end()#define fr(i,st,ed) for(int ist;ied;i)#define ffr(i,st,ed,dt) for(int ist;ied;idt)using namespace std;typedef pairint,stringPis;typedef pairint,intPii;typedef pairstring,stringPss;const int N2e410,mod1e97,M1e610;int lowbit(int x){return x(-x);}void solve(){int n;cinn;int m(n1)/2;int tnm;vectorintcnt(n1);fr(i,1,t){int x;cinx;cnt[x];}fr(i,1,n)if(cnt[i]0){cout-1\n;return;}vectorintrem(n1,0);fr(i,1,n)rem[i]cnt[i]-1;int sum0;fr(d,0,m-1){sumrem[m-d];if(d)sumrem[md];if(sumd){cout-1\n;return;}}int pm;setintzr,al;fr(i,1,n){al.insert(i);if(!rem[i])zr.insert(i);}vectorPiires;fr(stp,1,m-1){if(!al.count(p)||rem[p]0){cout-1\n;return;}rem[p]--;if(!rem[p]){zr.insert(p);}if(rem[p]){auto it1zr.lower_bound(p);auto it2zr.upper_bound(p);if(it1zr.begin()||it2zr.end()){cout-1\n;return;}int l*prev(it1),r*it2;res.pb({l,r});al.erase(l);al.erase(r);zr.erase(l);zr.erase(r);}else{auto ital.find(p);auto preit,sufnext(it);bool f0;if(pre!al.begin())f1,pre--;if(frem[*pre]){auto it2zr.upper_bound(p);if(it2zr.end()){cout-1\n;return;}int np*pre;int r*it2;res.pb({p,r});zr.erase(p);zr.erase(r);al.erase(p);al.erase(r);pnp;}else{if(sufal.end()||rem[*suf]0){cout-1\n;return;}auto it1zr.lower_bound(p);if(it1zr.begin()){cout-1\n;return;}int l*prev(it1);int np*suf;res.pb({p,l});zr.erase(p);zr.erase(l);al.erase(p);al.erase(l);pnp;}}}if(al.size()!1){cout-1\n;return;}reverse(all(res));coutp ;for(auto [x,y]:res){coutx y ;}cout\n;}signed main(){GG;int _t1;cin_t;while(_t--){solve();}}1007考虑循环位移某些数位相同把他们变成出现最多的那个数即可#includebits/stdc.h#define int long long#define inf 0x3f3f3f3f3f3f3f#define GG ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#define cnot coutNO\n#define cyes coutYES\n#define cans coutans\n#define pb push_back#define x0 first#define y0 second#define lc p1#define rc p1|1#define mem(a,b) memset(a,b,sizeof(a))#define sp(x) fixedsetprecision(x)#define all(v) v.begin(),v.end()#define fr(i,st,ed) for(int ist;ied;i)#define ffr(i,st,ed,dt) for(int ist;ied;idt)using namespace std;typedef pairint,stringPis;typedef pairint,intPii;typedef pairstring,stringPss;const int N2e410,mod1e97,M1e610;int lowbit(int x){return x(-x);}int GCD(int a,int b){if(b0)return a;return GCD(b,a%b);}void solve(){int n,d;cinnd;int gGCD(n,GCD(n,d)*2);string s;cins;vectorvectorintvec(g1,vectorint(26,0));vectorintsz(g1,0);fr(i,0,n-1){int jmin(i%g,g-1-i%g);vec[j][s[i]-a];sz[j];}int ans0;fr(i,0,g-1){int mx0;fr(j,0,25)mxmax(mx,vec[i][j]);anssz[i]-mx;}cans;}signed main(){GG;int _t1;cin_t;while(_t--){solve();}}1010线段树维护dp#includebits/stdc.h#define int long long#define inf 0x3f3f3f3f3f3f3f#define GG ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#define cnot coutNO\n#define cyes coutYES\n#define cans coutans\n#define pb push_back#define x0 first#define y0 second#define lc p1#define rc p1|1#define mem(a,b) memset(a,b,sizeof(a))#define sp(x) fixedsetprecision(x)#define all(v) v.begin(),v.end()#define fr(i,st,ed) for(int ist;ied;i)#define ffr(i,st,ed,dt) for(int ist;ied;idt)using namespace std;typedef pairint,stringPis;typedef pairint,intPii;typedef pairstring,stringPss;const int N5e510,mod998244353,M1e610;int lowbit(int x){return x(-x);}struct Node{int Mincnt,sum,lazy;};Node tree[N2];void up(int p){tree[p].Mincntmin(tree[lc].Mincnt,tree[rc].Mincnt);tree[p].sum0;if(tree[p].Mincnttree[lc].Mincnt)tree[p].sumtree[lc].sum;if(tree[p].Mincnttree[rc].Mincnt)tree[p].sumtree[rc].sum;tree[p].sum%mod;}void f(int p,int val){tree[p].Mincntval;tree[p].lazyval;}void down(int p,int l,int r){if(tree[p].lazy){f(lc,tree[p].lazy);f(rc,tree[p].lazy);tree[p].lazy0;}}void build(int p,int l,int r){if(lr){tree[p].Mincnt0;tree[p].sum0;tree[p].lazy0;return;}int mid(lr)1;build(lc,l,mid);build(rc,mid1,r);up(p);}void setval(int p,int l,int r,int pos,int val){if(lr){tree[p].sumval;return;}down(p,l,r);int mid(lr)1;if(posmid)setval(lc,l,mid,pos,val);else setval(rc,mid1,r,pos,val);up(p);}void upd(int p,int l,int r,int ql,int qr,int val){if(qllrqr){f(p,val);return;}down(p,l,r);int mid(lr)1;if(qlmid)upd(lc,l,mid,ql,qr,val);if(qrmid)upd(rc,mid1,r,ql,qr,val);up(p);}Node que(int p,int l,int r,int ql,int qr){if(qllrqr){return tree[p];}down(p,l,r);int mid(lr)1;bool fl0,fr0;Node L,R;if(qlmid){Lque(lc,l,mid,ql,qr);fl1;}if(qrmid){Rque(rc,mid1,r,ql,qr);fr1;}if(!fl)return R;if(!fr)return L;Node res;res.Mincntmin(L.Mincnt,R.Mincnt);res.sum0;if(res.MincntL.Mincnt)res.sumL.sum;if(res.MincntR.Mincnt)res.sumR.sum;res.sum%mod;return res;}int n;int dp[N];void init(int n){mem(dp,0);mem(tree,0);dp[0]1;}void solve(){cinn;init(n);vectorinta(n1,0);fr(i,1,n){cina[i];}build(1,1,n);vectorvectorintpos(n1);int L0;fr(i,1,n){int xa[i];autovpos[x];setval(1,1,n,i,dp[i-1]);if(v.size()){int l(v.size()4?v[v.size()-4]1:1),rv.back();upd(1,1,n,l,r,-1);}v.pb(i);int l(v.size()4?v[v.size()-4]1:1);upd(1,1,n,l,i,1);if(v.size()5)Lmax(L,v[v.size()-5]);Node RESque(1,1,n,L1,i);dp[i](RES.Mincnt0?RES.sum:0);}coutdp[n]\n;}signed main(){GG;int _t1;cin_t;while(_t--){solve();}}1011签到队友敲的#include bits/stdc.husing namespace std;using LL long long;#define endl \nLL mod998244353;LL ksm(LL a,LL n){LL res1;while(n){if(n1)resres*a%mod;n/2;aa*a%mod;}return res%mod;}void solve(){LL n,q;cinnq;vectorLLa(n1);LL cnt0;for(int i1;in;i){cina[i];cnta[i];}for(int i1;in;i){int u,v;cinuv;}while(q--){LL x;cinx;if(a[x])cout0endl;else coutcnt1endl;}}int main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);LL T1;// build();cinT;while(T--){solve();}}