T1 不相邻集合
做法一：设 \(f_i\) 表示到当前位置以 \(i\) 结尾的最长长度，\(s_i\) 表示以 \(i\) 开头的最长长度。有 \(a>b\Leftrightarrow f_a>f_b\Leftrightarrow s_a<s_b\)，有了这个性质就可以直接上线段树维护，时间复杂度 \(\mathcal{O}(n\log n)\)。
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
inline int read(){char ch=getchar();int x=0,f=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}
const int N=5e5+100,LEN=5e5+10;
int n,a[N];
struct TREE{int mx;}t[N<<2],f[N<<2];
inline void insert(int p,int l,int r,int pos,int x){
if(l==r){t[p].mx=x;return ;}
int mid=l+r>>1;
if(pos<=mid)insert(p<<1,l,mid,pos,x);
else insert(p<<1|1,mid+1,r,pos,x);
t[p].mx=std::max(t[p<<1].mx,t[p<<1|1].mx);
}
inline int query(int p,int l,int r,int L,int R){
if(L>R)return 0;
if(l>=L&&r<=R)return t[p].mx;
int res=0,mid=l+r>>1;
if(L<=mid)res=query(p<<1,l,mid,L,R);
if(R>mid)res=std::max(res,query(p<<1|1,mid+1,r,L,R));
return res;
}
inline void insert1(int p,int l,int r,int pos,int x){
if(l==r){f[p].mx=x;return ;}
int mid=l+r>>1;
if(pos<=mid)insert1(p<<1,l,mid,pos,x);
else insert1(p<<1|1,mid+1,r,pos,x);
f[p].mx=std::max(f[p<<1].mx,f[p<<1|1].mx);
}
inline int query1(int p,int l,int r,int L,int R){
if(L>R)return 0;
if(l>=L&&r<=R)return f[p].mx;
int res=0,mid=l+r>>1;
if(L<=mid)res=query1(p<<1,l,mid,L,R);
if(R>mid)res=std::max(res,query1(p<<1|1,mid+1,r,L,R));
return res;
}
signed main(){
// freopen("in.in","r",stdin);freopen("out.out","w",stdout);
std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
n=read();for(int i=1;i<=n;++i)a[i]=read();
for(int i=1;i<=n;++i){
int x=query(1,1,LEN,1,a[i]-2)+1;
insert(1,1,LEN,a[i],x);
x=query1(1,1,LEN,a[i]+2,LEN)+1;
insert1(1,1,LEN,a[i],x);
std::cout<<std::max(f[1].mx,t[1].mx)<<' ';
}
}
做法二：对于一个长度为 \(len\) 的极长连续段，答案为 \(\left\lceil \frac{len}{2}\right\rceil\)，然后不连续的段一定可以接在一起，所以对于一个序列，它的答案为 \(\sum \left\lceil \frac{len_i}{2}\right\rceil\)，可以用并查集维护连续段。
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
inline int read(){char ch=getchar();int x=0,f=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}
const int N=5e5+10;
int n,a[N],fa[N],size[N];
bool mp[N];
inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
inline void merge(int x,int y){
x=find(x),y=find(y);
if(size[x]>size[y])std::swap(x,y);
fa[x]=y;size[y]+=size[x];
}
inline int c(int x){return (x-1)/2+1;}
signed main(){
// freopen("in.in","r",stdin);freopen("out.out","w",stdout);
std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
n=read();for(int i=1;i<=n;++i)a[i]=read();
int ans=0;
for(int i=1;i<=5e5+5;++i)fa[i]=i,size[i]=1;
for(int i=1;i<=n;++i){
if(mp[a[i]]){std::cout<<ans<<' ';continue;}
else mp[a[i]]=1;
if(!mp[a[i]-1]&&!mp[a[i]+1])ans++;
if(mp[a[i]-1]&&!mp[a[i]+1]){
int sum1=size[find(a[i]-1)];
merge(a[i]-1,a[i]);
ans=ans-c(sum1)+c(sum1+1);
}
if(mp[a[i]+1]&&!mp[a[i]-1]){
int sum1=size[find(a[i]+1)];
merge(a[i]+1,a[i]);
ans=ans-c(sum1)+c(sum1+1);
}
if(mp[a[i]+1]&&mp[a[i]-1]){
int sum1=size[find(a[i]+1)],sum2=size[find(a[i]-1)];
int sum=sum1+sum2+1;
merge(a[i],a[i]+1),merge(a[i],a[i]-1);
ans=ans-c(sum1)-c(sum2)+c(sum);
}
std::cout<<ans<<' ';
}
}
T2 线段树
观察后发现，对于一个长度为 \(len\)，编号为 \(p\) 的节点，它的贡献为 \(k\cdot p+b\)，一次函数。\(k_{len}=2k_{mid-l+1}+2k_{r-mid},b_{len}=b_{mid-l+1}+b_{r-mid}+k_{r-mid}\) 记忆化搜索即可。
#include<bits/stdc++.h>
#define int long long
typedef long long ll;
typedef unsigned long long ull;
inline int read(){char ch=getchar();int x=0,f=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}
std::unordered_map<int,std::pair<int,int>> mp;
const int mod=1e9+7;
inline int mo(int x){return x<mod?x:x%mod;}
int T,n,x,y;
inline std::pair<int,int> work(int l,int r,int x,int y){
if(l>=x&&r<=y){
auto it=mp[r-l+1];
if(it.first){return it;}
int mid=l+r>>1;
auto ls=work(l,mid,x,y),rs=work(mid+1,r,x,y);
return mp[r-l+1]={mo(2*(ls.first+rs.first)+1),mo(ls.second+rs.first+rs.second)};
}
int mid=l+r>>1;std::pair<int,int> res={0,0};
if(x<=mid){auto ls=work(l,mid,x,y);res.first=mo(res.first+ls.first*2),res.second=mo(res.second+ls.second);}
if(y>mid){auto rs=work(mid+1,r,x,y);res.first=mo(res.first+rs.first*2),res.second=mo(res.second+rs.first+rs.second);}
return res;
}
signed main(){
// freopen("in.in","r",stdin);freopen("out.out","w",stdout);
std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
T=read();mp[1]={1,0};
while(T--){
n=read(),x=read(),y=read();
auto it=work(1,n,x,y);
std::cout<<mo(it.first+it.second)<<'\n';
}
}
T3 魔法师
小清新线段树题。
由于不知道答案是由谁贡献，所以很难来解决问题，考虑简单推下式子，对于法杖 \(p\) 和咒语 \(q\) 结合，当 \(a_p+a_q<b_p+b_q\) 时，有 \(a_p-b_p<b_q-a_q\)，设 \(u_p=a_p-b_p,u_q=b_q-a_q\)，这样根据 \(u_p\) 和 \(u_q\) 的大小关系，就可以确定答案由 \(a\) 贡献还是由 \(b\) 贡献，然后就能确定去最小的 \(a\) 还是最小的 \(b\)，此时以 \(u\) 为位置，用线段树维护区间最小的 \(a_p,a_q,b_p,b_q,ans\) 即可。修改使用 multiset 即可。
上传时 \(ans\) 用左区间的 \(b_p\) 加右区间的 \(b_q\) 和左区间的 \(a_q\) 加右区间的 \(a_p\) 来更新即可，（保证 \(u_p\) 和 \(u_q\) 的大小关系）。
#include<bits/stdc++.h>
#define ls p<<1
#define rs p<<1|1
typedef long long ll;
typedef unsigned long long ull;
inline int read(){char ch=getchar();int x=0,f=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}
const int N=2.5e5+10,LEN=5e5+5,P=2.5e5+1,inf=1e9;
int n,T,lastans,cnt;
std::multiset<int> sap[N],sbp[N],saq[N],sbq[N];
inline std::pair<int,int> get(std::pair<int,int> a,std::pair<int,int> b){return {std::min(a.first,b.first),std::min(a.second,b.second)};}
struct TREE{int ap,bp,aq,bq,res,id;}t[LEN<<2];
inline void update(int p){
t[p]={std::min(t[ls].ap,t[rs].ap),std::min(t[ls].bp,t[rs].bp),std::min(t[ls].aq,t[rs].aq),std::min(t[ls].bq,t[rs].bq),inf,0};
t[p].res=std::min(t[ls].res,t[rs].res);
t[p].res=std::min(t[p].res,std::min(t[ls].bp+t[rs].bq,t[rs].ap+t[ls].aq));
}
inline void build(int p,int l,int r){
t[p]={inf,inf,inf,inf,inf,0};
if(l==r)return ;
int mid=l+r>>1;build(ls,l,mid);build(rs,mid+1,r);
}
inline void change(int p,int l,int r,int pos,int a,int b,int pd,int flag){
if(l==r){
if(flag){
if(!t[p].id)t[p].id=++cnt,saq[cnt].insert(inf),sbq[cnt].insert(inf),sap[cnt].insert(inf),sbp[cnt].insert(inf);int x=t[p].id;
if(pd)saq[x].insert(a),sbq[x].insert(b);else{if(saq[x].find(a)!=saq[x].end()&&sbq[x].find(b)!=sbq[x].end())saq[x].erase(a),sbq[x].erase(b);}
t[p].aq=*saq[x].begin(),t[p].bq=*sbq[x].begin();
}else{
if(!t[p].id)t[p].id=++cnt,saq[cnt].insert(inf),sbq[cnt].insert(inf),sap[cnt].insert(inf),sbp[cnt].insert(inf);int x=t[p].id;
if(pd)sap[x].insert(a),sbp[x].insert(b);else{if(sap[x].find(a)!=sap[x].end()&&sbp[x].find(b)!=sbp[x].end())sap[x].erase(a),sbp[x].erase(b);}
t[p].ap=*sap[x].begin(),t[p].bp=*sbp[x].begin();
}
t[p].res=t[p].bp+t[p].bq;
return;
}
int mid=l+r>>1;
if(pos<=mid)change(ls,l,mid,pos,a,b,pd,flag);
else change(rs,mid+1,r,pos,a,b,pd,flag);
update(p);
}
signed main(){
// freopen("in.in","r",stdin);freopen("out.out","w",stdout);
std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
n=read();T=read();build(1,1,LEN);
for(int i=1;i<=n;++i){
int op=read(),tt=read(),a=read(),b=read();
if(T)a^=lastans,b^=lastans;
if(op==2){op=0;}
if(tt)change(1,1,LEN,b-a+P,a,b,op,tt);else change(1,1,LEN,a-b+P,a,b,op,tt);
lastans=t[1].res;
if(lastans>=inf)lastans=0;std::cout<<lastans<<'\n';
}
}
T4 园艺
神秘题，\(f_{i,j,0/1}\) 表示拔草区间在 \([i,j]\)，左右端点时，拔草长度和未拔草长度的最小值，复杂度 \(\mathcal{O}(n^2)\)，没啥可优化的地方了。
发现对于每棵草，它的贡献就是到它之前走过的距离，设 \(f_i\) 表示到达 \(i\) 位置时，剩下所有草的长度加上所有草到当前位置的距离的最小值。靠近一棵草时，它的贡献不变，远离一棵草时，它会增加远离距离乘上 \(2\) 的贡献，设 \(i<j\)，\(s\) 表示前缀和，有
需要来模拟 dij 来转移，由于拔草区间为 \([l,r],l\le k\le r\)，且从 \(k\) 往两边延伸，\(f_i\) 递增。所以区间 \([l,r]\) 中的 \(f\) 值是松弛好的，每次需要更新的点为 \(f_{l-1},f_{r+1}\)，更新两者之后中的较小值为松弛好的点。这样省去了找到最小值的 \(\mathcal{O}(n)\)，但是转移的复杂度没变，简单推下转移式子，发现是斜率优化，可以做到均摊 \(\mathcal{O}(1)\) 转移。整体时间复杂度为 \(\mathcal{O}(n)\)。
#include<bits/stdc++.h>
#define int __int128
typedef long long ll;
typedef unsigned long long ull;
inline int read(){char ch=getchar();int x=0,f=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}
const int N=2e6+10,inf=9e18;
int f[N],d[N],s[N],n,k,L,R,qi[N],headi=1,taili,qj[N],headj=1,tailj;
bool vis[N];
inline int Abs(int i){return i<0?-i:i;}
inline int Yi(int i){return f[i]-2*(i-1)*s[i];}
inline int Yj(int j){return f[j]+2*(n-j)*s[j];}
inline int calcj(int i,int j){return f[i]+2*(i-1)*(s[j]-s[i]);}
inline int calci(int j,int i){return f[j]+2*(n-j)*(s[j]-s[i]);}
signed main(){
// freopen("in.in","r",stdin);freopen("out.out","w",stdout);
std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
n=read();k=read();for(int i=2;i<=n;++i)d[i]=read(),s[i]=s[i-1]+d[i];
memset(f,0x3f,sizeof(f));f[k]=0;for(int i=1;i<=n;++i)f[k]+=Abs(s[k]-s[i]);
std::queue<int> q;q.push(k);L=k,R=k;
while(!q.empty()){
int x=q.front();q.pop();
L=std::min(L,x);R=std::max(R,x);
int i=L-1,j=R+1;
if(L==1||R==n)break;
if(x<=k){while(headi<taili&&(Yi(qi[taili])-Yi(x))*(qi[taili-1]-qi[taili])>=(Yi(qi[taili-1])-Yi(qi[taili]))*(qi[taili]-x))taili--;qi[++taili]=x;}
while(headi<taili&&calcj(qi[headi],j)>=calcj(qi[headi+1],j))headi++;f[j]=calcj(qi[headi],j);
if(x>=k){while(headj<tailj&&(Yj(x)-Yj(qj[tailj]))*(qj[tailj]-qj[tailj-1])<=(Yj(qj[tailj])-Yj(qj[tailj-1]))*(x-qj[tailj]))tailj--;qj[++tailj]=x;}
while(headj<tailj&&calci(qj[headj],i)>=calci(qj[headj+1],i))headj++;f[i]=calci(qj[headj],i);
q.push(f[i]>f[j]?j:i);
}
std::cout<<(ll)std::min(f[1],f[n])<<'\n';
}
总结
T1 没签上到是我 shaber，后面暴力没打好是我 shaber，T3 set 没开好调半天是我 shaber，T4 压行把句子写 if 外面了是我 shaber，总结：我就是个 shaber。