原题大战
T1
范围 \(n\leq 10^{14}\)。
不用动脑，打个表找找规律。
考虑一个数 \(x\)，在 \(1\sim n\) 中包含 \(x\) 这个约数的个数为 \(\left\lfloor \dfrac{n}{x} \right\rfloor\)，那么既然是异或，只需要判断奇偶性算贡献即可。然后你发现这玩意显然可以整除分块，算连续一段贡献，只需要考虑相邻两个异或为 \(1\)，分讨一下即可。
Code
#include<bits/stdc++.h>
#define il inline
#define rint register int
#define int long long
using namespace std;
const int N=1e7+10,INF=2147483647;
char *p1,*p2,buf[N];
#define nc() (p1==p2 && (p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
#define gc() getchar()
il int rd(){
int x=0,f=1;
char ch=gc();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=gc();
return x*f;
}
int n,ans;
int get(int l,int r){
int len=(r-l+1);
if(!(l&1)){
if(len&1){
return ((len/2)&1)^r;
}else return ((len/2)&1);
}
else{
if(len&1){
return ((len/2)&1)^l;
}else return l^r^((len/2)&1?0:1);
}
}
void Main(){
n=rd();
/* int t=0,an=0,B=0,P=0;
for(int i=1; i<=n; ++i){
int cnt=n/i;
if(cnt&1)B^=i,a[++t]=i;
}
cout<<B<<endl<<t<<endl;
for(int i=1; i<=t; ++i){
int now=i,A=a[now];
while(a[now]+1==a[now+1])now++,A^=a[now];
cout<<A<<' '<<a[i]<<' '<<a[now]<<endl;an^=A;++P;
i=now;
}
cout<<endl<<an<<' '<<P<<endl;*/
int ans=0;
for(int l=1,r; l<=n; l=r+1){
r=n/(n/l);
if((n/l)&1)ans^=get(l,r);
// cout<<l<<' '<<r<<endl;
}
cout<<ans;
}
signed main(){
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
int T=1;
while(T--)Main();
return 0;
}
T2
原题：Uoj 面基之路。
\(n,m\leq 2\times 10^5,k\leq 20\)
转化一下，所有鸡（包括鸡妈妈）走到同一点用时最大的鸡的最小值。由于 \(k\) 很小，考虑预处理出所有鸡的单源最短路。然后貌似做完了？枚举点上的好处理。接着来考虑边 \((u,v)\)，思考一下，发现肯定是根据到 \(u\) 的时间从小到大，取前面连续的一段走 \(u\)，后一段连续的走 \(v\)，这样一定是最优的，枚举断点解决。时间复杂度 \(O(kn\log n+m\log k)\)。
Code
#include<bits/stdc++.h>
#define il inline
#define rint register int
#define ll long long
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
using namespace std;
const int N=1e5+10;const ll INF=1e18;
char *p1,*p2,buf[N];
#define nc() (p1==p2 && (p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
#define gc() getchar()
il ll rd(){
ll x=0,f=1;
char ch=gc();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=gc();
return x*f;
}
int n,m,k;
struct Edge{
int to,nxt;ll w;int fr;
}e[N<<2];
int head[N],tot_e;
void add(int x,int y,ll z){
e[++tot_e]={y,head[x],z,x};
head[x]=tot_e;
}
struct dat{
ll s;int id;
friend bool operator<(dat a,dat b){
return a.s>b.s;
}
}b[N];
ll dis[N],D[21][N];
bool vis[N];
void Dij(int S){
priority_queue<dat>q;
q.push({0,S});
for(int i=1; i<=n; ++i)vis[i]=0,dis[i]=INF;
dis[S]=0;
while(!q.empty()){
dat tmp=q.top();
q.pop();
int x=tmp.id;
if(vis[x])continue;
vis[x]=1;
for(int i=head[x]; i; i=e[i].nxt){
int y=e[i].to;
if(dis[y]>dis[x]+e[i].w){
dis[y]=dis[x]+e[i].w;
q.push({dis[y],y});
}
}
}
}
int id[N];
ll pre[N],suf[N];
void Main(){
n=rd(),m=rd();ll w;
for(int u,v,i=1; i<=m; ++i){
u=rd(),v=rd(),w=1ll*rd()*2;
add(u,v,w),add(v,u,w);
}
k=rd();
for(int i=1; i<=k; ++i){
id[i]=rd();
}
id[0]=1;
for(int i=0; i<=k; ++i){
Dij(id[i]);
for(int j=1; j<=n; ++j)D[i][j]=dis[j];
}
ll Ans=INF;
for(int i=1; i<=n; ++i){
ll ans=0;
for(int j=0; j<=k; ++j){
ans=max(ans,D[j][i]);
}
Ans=min(Ans,ans);
// cout<<ans<<endl;
}
for(int i=1; i<=tot_e; i+=2){
int x=e[i].fr,y=e[i].to;ll z=e[i].w;
for(int j=0; j<=k; ++j){
b[j]={D[j][x],j};
}
sort(b,b+1+k);
pre[0]=D[b[0].id][y];
for(int j=1; j<=k; ++j){
pre[j]=max(pre[j-1],D[b[j].id][y]);
}
suf[k+1]=0;
for(int j=k; j>=0; --j){
suf[j]=max(suf[j+1],b[j].s);
}
/* for(int j=0; j<=k; ++j)cout<<b[j].s<<' ';
cout<<endl;
for(int j=0; j<=k; ++j)cout<<D[b[j].id][y]<<' ';
cout<<endl;
for(int j=0; j<=k; ++j)cout<<pre[j]<<' ';
cout<<endl;
for(int j=0; j<=k; ++j)cout<<suf[j]<<' ';
cout<<endl;*/
for(int j=0; j<k; ++j){
ll L=pre[j],R=suf[j+1];
if(L>R)swap(L,R);
if(L+z<=R)Ans=min(Ans,R);
else Ans=min(Ans,(L+R+z)/2);
// cout<<x<<' '<<y<<' '<<L<<' '<<R<<' '<<j<<' '<<Ans<<endl;
}
}
cout<<Ans;
}
signed main(){
freopen("b.in","r",stdin);
freopen("b.out","w",stdout);
int T=1;
while(T--)Main();
return 0;
}
/*
4 6
1 4 400000000000
2 3 400000000000
3 4 100000000000
3 1 200000000000
1 2 100000000000
2 4 400000000000
2
2 3
*/
T3
\(n,q,k\leq 2\times 10^5,p_i\leq 10^9\)
好 \(\color{red}\mathtt{trick}\)。
首先考虑转化，由于串只有 \(01\) 组成，那么我们的 \(LIS\) 一定是一段 \(0\) 接一段 \(1\) 的形式，那我们记中间的断点位置为 \(i\)，将 \(LIS\) 长度表示为 \(i\) 后面 \(1\) 的个数 \(+\) \(i\) 前面 \(0\) 的个数。然后这个式子还是有点丑，考虑转成一元形式：将 \(01\) 串中 \(1\) 赋值贡献为 \(-1\)，\(0\) 赋值贡献为 \(1\)，将这个权值做个前缀和 \(w_i\)，那么 \(LIS\) 长度就可以表示成 \(w_i+cnt_1\)，其中 \(cnt_1\) 是整个串中 \(1\) 的个数。回到原问题，加上了 \(k\) 次翻转，我们又该如何应对？其实在翻转了 \(k\) 次的串上取一段前缀相当于在原串上取一段前缀加上 \(k\) 段不相交的区间。那么我们这时就好做了，考虑贪心，首先选一个权值和最⼤的前缀，并将前缀中的所有权值取反，然后每次选取⼀个权值和最⼤的⼦区间，同样也将权值取反。这里取反相当于再次选中时抵消贡献，满足区间不相交。然后维护子区间最大值很简单，经典问题，线段树即可。
Code
#include<bits/stdc++.h>
#define il inline
#define rint register int
#define int long long
using namespace std;
const int N=2e5+10,INF=1e18;
char *p1,*p2,buf[N];
#define nc() (p1==p2 && (p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
#define gc() getchar()
il int rd(){
int x=0,f=1;
char ch=gc();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=gc();
return x*f;
}
int n,m,ans;
int p[N],c[N],k[N],s[N],Ans[N];
struct Dat{
int l,r,w;
friend Dat operator +(Dat A,Dat B){
Dat C;
C.l=A.l,C.r=B.r;C.w=A.w+B.w;
return C;
}
friend bool operator<(Dat A,Dat B){
return A.w<B.w;
}
};
Dat Max(Dat A,Dat B){
return A<B?B:A;
}
Dat Min(Dat A,Dat B){
return A<B?A:B;
}
struct Seg_tr{
int tag,l,r;
Dat s,wl,wr,w,_s,_wl,_wr,_w;
}tr[N<<2];
void push_up(int k){
tr[k].w=Max(tr[k<<1].w,tr[k<<1|1].w);
tr[k].w=Max(tr[k].w,tr[k<<1].wr+tr[k<<1|1].wl);
tr[k].wl=Max(tr[k<<1].wl,tr[k<<1].s+tr[k<<1|1].wl);
tr[k].wr=Max(tr[k<<1|1].wr,tr[k<<1].wr+tr[k<<1|1].s);
tr[k]._w=Max(tr[k<<1]._w,tr[k<<1|1]._w);
tr[k]._w=Max(tr[k]._w,tr[k<<1]._wr+tr[k<<1|1]._wl);
tr[k]._wl=Max(tr[k<<1]._wl,tr[k<<1]._s+tr[k<<1|1]._wl);
tr[k]._wr=Max(tr[k<<1|1]._wr,tr[k<<1]._wr+tr[k<<1|1]._s);
tr[k].s=tr[k<<1].s+tr[k<<1|1].s;
tr[k]._s=tr[k<<1]._s+tr[k<<1|1]._s;
}
void push_tag(int k){
swap(tr[k].s,tr[k]._s);
swap(tr[k].w,tr[k]._w);
swap(tr[k].wl,tr[k]._wl);
swap(tr[k].wr,tr[k]._wr);
tr[k].tag^=1;
}
void push_down(int k){
if(tr[k].tag){
push_tag(k<<1);
push_tag(k<<1|1);
tr[k].tag^=1;
}
}
void build(int k,int l,int r){
tr[k].l=l,tr[k].r=r;
if(l==r){
tr[k].w=tr[k].wl=tr[k].wr=tr[k].s={l,r,((c[l]==1)?-1:1)*p[l]};
tr[k]._w=tr[k]._wl=tr[k]._wr=tr[k]._s={l,r,((c[l]==1)?1:-1)*p[l]};
return ;
}
int mid=(l+r)>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
push_up(k);
}
void change(int k,int L,int R){
if(L>R)return;
if(tr[k].l>=L&&tr[k].r<=R){
push_tag(k);
return;
}
push_down(k);
int mid=(tr[k].l+tr[k].r)>>1;
if(L<=mid)change(k<<1,L,R);
if(R>mid)change(k<<1|1,L,R);
push_up(k);
}
void Main(){
n=rd();
for(int i=1; i<=n; ++i){
c[i]=rd(),p[i]=rd();
if(c[i]==1)ans+=p[i];
s[i]=s[i-1]+((c[i]==1)?-1:1)*p[i];
}
build(1,1,n);
int ma=0,pos=0;
for(int i=1; i<=n; ++i){
if(s[i]>ma)ma=s[i],pos=i;
}
ans+=s[pos];
change(1,1,pos);
Ans[0]=ans;
m=rd();int T=0;
for(int i=1; i<=m; ++i){
k[i]=rd();T=max(T,k[i]);
}
for(int i=1; i<=T; ++i){
int l=tr[1].w.l,r=tr[1].w.r,w=tr[1].w.w;
Ans[i]=max(Ans[i-1],Ans[i-1]+w);
if(w>0)
change(1,l,r);
}
for(int i=1; i<=m; ++i)printf("%lld\n",Ans[k[i]]);
}
signed main(){
freopen("c.in","r",stdin);
freopen("c.out","w",stdout);
int T=1;
while(T--)Main();
return 0;
}