2023大联盟6比赛总结

比赛链接

反思

A

为什么打表就我看不出规律！！！
定式思维太严重了T_T

B

纯智障分块题，不知道为什么 $B=100$ 比理论最优 $B=300$ 更优（快了 3 倍），看来分块还是要学习一些卡常技巧的

C

菜死了，不会

D

菜死了，不会

题解

A

神奇的式子，考虑打表
打表！！！
可以发现一下两个规律：

1. 只有当 $x+y$ 是 $2$ 的次幂时 $f(x,y)$ 才可能不为 $0$
2. $f(x,y)=f(\frac{x}{d},\frac{y}{d})$，其中 $d=\gcd (x,y)$
   且若 $x+y=2^k,x,y$ 都为奇数且 $(x,y)=1$ 时，$f(x,y)=k$

考虑证明：
考虑 $x+y$ 必须为偶数因为一直循环下去 $x+y$ 的值不变
$f(x,y)=f(\frac{x}{d},\frac{y}{d})$ 是易得的
我们只需要考虑 $x,y$ 都为奇数的情况，因为 $x,y$ 为偶数时 $2|\gcd (x,y)$
令 $x>y$，则 $f(x,y)=f(2y,x-y)+1$
因为 $2y,x-y$ 都为偶数，所以 $f(x,y)=f(y,\frac{x-y}{2})+1$
这样 $x^{\prime }+y^{\prime }$ 的值就除了 $2$，且因为 $\gcd (x,y)=1$，所以 $\gcd (y,\frac{x-y}{2})=1$
所以 $x+y$ 只有当是 $2$ 的次幂时，$x^{\prime }=y^{\prime }$，且操作次数为 $lo{g}_2(x+y)$

我们发现这有值的点对个数是 $O(nlogn)$ 级别的
所以我们可以把所有有值的点对找出来，然后询问就相当于二维数点了
离线询问 + 扫描线 + 树状数组即可
时间复杂度 $O(nlo{g}^{2}n)$

#include <bits/stdc++.h>
#define pb push_back
#define lowbit(x) x&-x
using namespace std;
typedef long long LL;
const int N=300100,Q=1000100;
struct Node{ int p1,p2,val;};
struct Node2{ int l,r,id,coef;};
int n,p[N],b[N];
LL tr[N],ans[Q];
Node used[N*40];
vector<Node2> query[N];
inline int read(){int FF=0,RR=1;char ch=getchar();for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;return FF*RR;
}
bool cmp(const Node &x,const Node &y){ return x.p1<y.p1;}
void add(int x,int v){ for(;x<=n;x+=lowbit(x)) tr[x]+=v;}
LL ask(int x){if(x<=0) return 0;LL res=0;for(;x;x-=lowbit(x)) res+=tr[x];return res;
}
int main(){freopen("perm.in","r",stdin);freopen("perm.out","w",stdout);n=read();for(int i=1;i<=n;i++) p[i]=read(),b[p[i]]=i;int cnt=0;for(int pw=4,mi=2;pw<=n<<1;pw<<=1,mi++)for(int x=1;x<=pw;x+=2){int y=pw-x;for(int k=1;k*max(x,y)<=n;k++) used[++cnt]={b[x*k],b[y*k],mi};}int q=read();for(int i=1;i<=q;i++){int l=read(),r=read();query[l-1].pb({l,r,i,-1}),query[r].pb({l,r,i,1});}sort(used+1,used+cnt+1,cmp);for(int i=1,j=0;i<=n;i++){while(j<cnt&&used[j+1].p1<=i){j++;assert(used[j].p2>=1&&used[j].p2<=n);add(used[j].p2,used[j].val);}for(Node2 t:query[i]) ans[t.id]+=t.coef*(ask(t.r)-ask(t.l-1));}for(int i=1;i<=q;i++) printf("%lld\n",ans[i]/2);fprintf(stderr,"%d ms\n",int(1e3*clock()/CLOCKS_PER_SEC));return 0;
}

B

不说了，思想比较简单，就是分块 + 块内用优先队列维护
时间复杂度 $O(n\sqrt{m}logn)$，$m$ 为修改操作个数
块长设为 $100$ 实测最优

#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
const int N=100100,MAXB=1010,P=1e9+7;
typedef pair<int,int> pii;
int n,m,a[N],pref[N],pos[N];
int B,sum[MAXB],tot[MAXB],tag[MAXB],_l[MAXB],_r[MAXB];
priority_queue<pii,vector<pii>,greater<pii> > pq[MAXB];
inline int read(){int FF=0,RR=1;char ch=getchar();for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;return FF*RR;
}
inline int calc(int x){int cur=sqrt(x);return (pref[cur-1]+1ll*(x-cur*cur+1)*cur)%P;
}
inline void inc(int &x,int y){ x+=y;if(x>=P) x-=P;}
void rebuild(int Block){for(int i=_l[Block];i<=_r[Block];i++) a[i]+=tag[Block];tag[Block]=tot[Block]=sum[Block]=0;while(!pq[Block].empty()) pq[Block].pop();for(int i=_l[Block];i<=_r[Block];i++){int sq=sqrt(a[i]);inc(tot[Block],calc(a[i])),inc(sum[Block],sq);pq[Block].emplace(make_pair((sq+1)*(sq+1)-a[i],i));}assert(tot[Block]>=0);
}
void modify(int l,int r){if(pos[l]==pos[r]){for(int i=l;i<=r;i++) a[i]++;rebuild(pos[l]);return;}else{int i=l,j=r;while(pos[i]==pos[l]) a[i]++,i++;while(pos[j]==pos[r]) a[j]++,j--;rebuild(pos[l]),rebuild(pos[r]);for(int k=pos[i];k<=pos[j];k++){tag[k]++;pii t=pq[k].top();while(t.first<=tag[k]){pq[k].pop();inc(sum[k],1);int v=sqrt(a[t.second]+tag[k]);assert(v*v==a[t.second]+tag[k]);pq[k].push(make_pair((v+1)*(v+1)-a[t.second],t.second));t=pq[k].top();}inc(tot[k],sum[k]);}}
}
int query(int l,int r){int ans=0;if(pos[l]==pos[r]){rebuild(pos[l]);for(int i=l;i<=r;i++) inc(ans,calc(a[i]));}else{rebuild(pos[l]),rebuild(pos[r]);int i=l,j=r;while(pos[i]==pos[l]) inc(ans,calc(a[i])),i++;while(pos[j]==pos[r]) inc(ans,calc(a[j])),j--;for(int k=pos[i];k<=pos[j];k++) inc(ans,tot[k]);}return ans;
}
int main(){freopen("play.in","r",stdin);freopen("play.out","w",stdout);for(int i=1;i<=40000;i++) pref[i]=(pref[i-1]+((1ll*(i+1)*(i+1)-1ll*i*i)%P+P)*i)%P;for(int i=1;i<=40000;i++) assert(pref[i]>=0);n=read(),m=read();for(int i=1;i<=n;i++) a[i]=read();B=100;for(int i=1;i<=n;i++) pos[i]=(i-1)/B+1;for(int i=1;i<=pos[n];i++) _l[i]=_r[i-1]+1,_r[i]=i*B;_r[pos[n]]=n;for(int i=1;i<=pos[n];i++) rebuild(i);for(int i=1;i<=m;i++){int op=read(),l=read(),r=read();if(op==1) modify(l,r);else printf("%d\n",query(l,r));}fprintf(stderr,"%d ms\n",int(1e3*clock()/CLOCKS_PER_SEC));return 0;
}

C

感觉是到有点 nb 的题
不考虑翻转，如何求 $lis$？
考虑枚举分界点 $i$，那么答案 = max ⁡ { i 前面 0 的个数 + i 后面 1 的个数 } =\max\{i前面0的个数+i后面1的个数\} =max{i前面0的个数+i后面1的个数}
这等价于 $s1+\underset{i=1}{\overset{n}{\max }}su{m}_i$，其中 $s1$ 为序列中 $1$ 的个数，$su{m}_i$ 为把 $0$ 的权值设为 $1$，$1$ 的权值设为 $-1$ 的前缀和

考虑翻转操作
我们可以把这个问题等价地看成选出一段前缀和与 $m$ 段不相交子区间（不能与前缀相交）的和的最大值
这一步感觉很难想，也很难理解
具体我也不会证，只能自己画图感性理解

然后就是经典的反悔贪心操作了，找最大的区间，然后区间取反，用线段树维护即可
时间复杂度 $O(nlogn)$

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=200100;
int n,val[N],s[N];
inline int read(){int FF=0,RR=1;char ch=getchar();for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;return FF*RR;
}
struct Node{int l,r,sum;int lmx,rmx,mx,Lp,Rp,LLp,RRp;int lmn,rmn,mn,Lq,Rq,LLq,RRq;bool tag;
}seg[N<<2];
Node operator +(const Node &lc,const Node rc){Node ret;ret.l=lc.l,ret.r=rc.r,ret.tag=0;ret.sum=lc.sum+rc.sum;ret.lmx=lc.lmx,ret.LLp=lc.LLp;if(lc.sum+rc.lmx>ret.lmx) ret.lmx=lc.sum+rc.lmx,ret.LLp=rc.LLp;ret.rmx=rc.rmx,ret.RRp=rc.RRp;if(rc.sum+lc.rmx>ret.rmx) ret.rmx=rc.sum+lc.rmx,ret.RRp=lc.RRp;ret.mx=lc.rmx+rc.lmx,ret.Lp=lc.RRp,ret.Rp=rc.LLp;if(lc.mx>ret.mx) ret.mx=lc.mx,ret.Lp=lc.Lp,ret.Rp=lc.Rp;if(rc.mx>ret.mx) ret.mx=rc.mx,ret.Lp=rc.Lp,ret.Rp=rc.Rp;ret.lmn=lc.lmn,ret.LLq=lc.LLq;if(lc.sum+rc.lmn<ret.lmn) ret.lmn=lc.sum+rc.lmn,ret.LLq=rc.LLq;ret.rmn=rc.rmn,ret.RRq=rc.RRq;if(rc.sum+lc.rmn<ret.rmn) ret.rmn=rc.sum+lc.rmn,ret.RRq=lc.RRq;ret.mn=lc.rmn+rc.lmn,ret.Lq=lc.RRq,ret.Rq=rc.LLq;if(lc.mn<ret.mn) ret.mn=lc.mn,ret.Lq=lc.Lq,ret.Rq=lc.Rq;if(rc.mn<ret.mn) ret.mn=rc.mn,ret.Lq=rc.Lq,ret.Rq=rc.Rq;return ret;
}
void down(int x){swap(seg[x].lmx,seg[x].lmn),swap(seg[x].rmx,seg[x].rmn),swap(seg[x].mx,seg[x].mn);swap(seg[x].Lp,seg[x].Lq),swap(seg[x].Rp,seg[x].Rq),swap(seg[x].LLp,seg[x].LLq),swap(seg[x].RRp,seg[x].RRq);seg[x].sum*=-1,seg[x].lmx*=-1,seg[x].rmx*=-1,seg[x].mx*=-1,seg[x].lmn*=-1,seg[x].rmn*=-1,seg[x].mn*=-1;seg[x].tag^=1;
}
void pushdown(int x){if(seg[x].tag) down(x<<1),down(x<<1^1);seg[x].tag=0;
}
void build(int l,int r,int x){if(l==r){ seg[x]={l,l,val[l],val[l],val[l],val[l],l,l,l,l,val[l],val[l],val[l],l,l,l,l,0};return;}int mid=(l+r)>>1; build(l,mid,x<<1),build(mid+1,r,x<<1^1);seg[x]=seg[x<<1]+seg[x<<1^1];
}
void modify(int l,int r,int x,int L,int R){if(L<=l&&r<=R){ down(x);return;}pushdown(x);int mid=(l+r)>>1;if(mid>=L) modify(l,mid,x<<1,L,R);if(mid<R) modify(mid+1,r,x<<1^1,L,R);seg[x]=seg[x<<1]+seg[x<<1^1];
}
signed main(){freopen("lis.in","r",stdin);freopen("lis.out","w",stdout);n=read();int ans=0;for(int i=1;i<=n;i++){int a=read(),b=read();if(a==0) a=1;else a=-1,ans+=b;val[i]=a*b,s[i]=s[i-1]+val[i];}int mx=0;s[0]=-1e18;for(int i=1;i<=n;i++) if(s[i]>s[mx]) mx=i;build(1,n,1);if(s[mx]>0) ans+=s[mx],modify(1,n,1,1,mx);printf("%lld\n",ans);int m=read();for(int i=1;i<=m;i++){Node ret=seg[1];if(ret.mx>0) ans+=ret.mx,modify(1,n,1,ret.Lp,ret.Rp);printf("%lld\n",ans);}fprintf(stderr,"%d ms\n",int64_t(1e3*clock()/CLOCKS_PER_SEC));return 0;
}

D

考虑暴力是 $f_{i,j}$ 表示当前在 $i$，前一个选 $j$ 的最大长度，因为 $p_i\ne k$ 的限制很松，所以直接记录最大值和次大值就可以维护，时间复杂度 $O(n^3)$

于是我们可以猜测需要保留的转移状态不会太多，事实上是真的
我们令三元组 $(lenth,pre,i)$ 表示当前在 $i$，上一个在 $pre$，长度为 $lenth$ 的状态
我们考虑用这个东西转移
每次答案，我们需要把 $a_j<a_i$ 的 $(lenth,pre,j)$ 取出，然后更新 $i$ 的状态
结论1：对于 $i$ 只需要保留 $lenth$ 最长的两个且满足 $j_p\ne j_q$ 的状态
首先 $j$ 相等的状态只需要保留一个，那么后面最多只会排除掉 $1$ 个状态，所以只需要暴力 $2$ 个状态
结论2：只需要取出 $(lenth,pre,j)$ 的前 $5$ 大 $lenth$，且对于 $pre$ 相同的，我们只保留最大的 $2$ 个
为什么，考虑如果前两个的 $pre$ 都和 $i$ 一样，那么后两个必然有两个 $pre$ 不相同的，是可以更新出 $2$ 个有效答案的

时间复杂度 $O(nlogn)$（但常数有点大，我稍微卡了一下常）

#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define pb push_back
#define lowbit(x) x&-x
using namespace std;
const int N=200100;
inline int read(){int FF=0,RR=1;char ch=getchar();for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;return FF*RR;
}
struct Node{ int lenth,pre,x;//以x结尾的长度为lenth的序列，前一个为pre的一种转移
};
vector<Node> tr[N];
int n,a[N],p[N],cnt[N];
bool cmp(const Node &o1,const Node &o2){ return o1.lenth>o2.lenth;}
auto select(vector<Node> vec){sort(vec.begin(),vec.end(),cmp);vector<Node> ret;for(auto t:vec){int c=0;for(auto q:ret) if(q.pre==t.pre) c++;if(c==2) continue;ret.pb(t);if(ret.size()==5) break;}return ret;
}
const int B=20;
void add(int x,vector<Node> ad){for(;x<=n;x+=lowbit(x)){for(auto t:ad) tr[x].pb(t);if(tr[x].size()>=B) tr[x]=select(tr[x]);}
}
auto query(int x){vector<Node> ret;for(;x;x-=lowbit(x)) for(auto t:tr[x]) ret.pb(t);return ret;
}
void work(){n=read();for(int i=1;i<=n;i++) a[i]=read();for(int i=1;i<=n;i++) p[i]=read();int ans=0;for(int i=1;i<=n;i++){auto ret=query(a[i]-1);ret.pb({0,-1,-1});//以i为开头ret=select(ret);vector<Node> cur;for(auto t:ret)if(p[i]!=t.pre)if(!cur.size()||t.x!=cur.back().pre){cur.pb({t.lenth+1,t.x,i});if(cur.size()==2) break;}for(auto t:cur) ans=max(ans,t.lenth);add(a[i],cur);}printf("%d\n",ans);for(int i=1;i<=n;i++) tr[i].clear();
}
int main(){freopen("cactus.in","r",stdin);freopen("cactus.out","w",stdout);int T=read();while(T--) work();fprintf(stderr,"%d ms\n",int(1e3*clock()/CLOCKS_PER_SEC));return 0;
}