A. Square Function
留坑。
B. Guess by Remainder
询问$lcm(1,2,3,...,n)-1$即可一步猜出数。
计算$lcm$采用分治FFT即可，时间复杂度$O(n\log^2n)$。
C. Subtract if Greater!
对于每个修改操作，$[1,x]$的数无需修改，$[x+1,2x]$的数会减小至少一半，暴力修改即可，$[2x+1,inf]$的数减小之后排名不变，故可以在平衡树上打标记实现。
时间复杂度$O(n\log^2n+m\log n)$。
#include<cstdio>
#include<algorithm>
const int N=100010,inf=~0U>>1;
int n,m,i,op,k,a[N],val[N],tag[N],size[N],son[N][2],f[N],tot,root;
inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}
inline void add1(int x,int p){
if(!x)return;
val[x]+=p;
tag[x]+=p;
}
inline void pb(int x){
if(tag[x]){
add1(son[x][0],tag[x]);
add1(son[x][1],tag[x]);
tag[x]=0;
}
}
inline void up(int x){
size[x]=1;
if(son[x][0])size[x]+=size[son[x][0]];
if(son[x][1])size[x]+=size[son[x][1]];
}
inline void rotate(int x){
int y=f[x],w=son[y][1]==x;
son[y][w]=son[x][w^1];
if(son[x][w^1])f[son[x][w^1]]=y;
if(f[y]){
int z=f[y];
if(son[z][0]==y)son[z][0]=x;
if(son[z][1]==y)son[z][1]=x;
}
f[x]=f[y];son[x][w^1]=y;f[y]=x;up(y);
}
inline void splay(int x,int w){
int s=1,i=x,y;a[1]=x;
while(f[i])a[++s]=i=f[i];
while(s)pb(a[s--]);
while(f[x]!=w){
y=f[x];
if(f[y]!=w){if((son[f[y]][0]==y)^(son[y][0]==x))rotate(x);else rotate(y);}
rotate(x);
}
if(!w)root=x;
up(x);
}
int build(int l,int r,int fa){
int x=++tot,mid=(l+r)>>1;
f[x]=fa;val[x]=a[mid];
if(l<mid)son[x][0]=build(l,mid-1,x);
if(r>mid)son[x][1]=build(mid+1,r,x);
up(x);
return x;
}
inline void ask(int k){
int x=root,t;
while(x){
pb(x);
if(val[x]>k)t=x,x=son[x][0];else x=son[x][1];
}
splay(t,0);
}
void ins(int&x,int y,int fa){
if(!x){
x=y;
f[y]=fa;
return;
}
pb(x);
size[x]++;
if(val[y]<val[x])ins(son[x][0],y,x);else ins(son[x][1],y,x);
}
inline void change(int k){
while(1){
ask(k);
int x=root;
if(val[x]<=k*2){
int y=son[x][1];
while(son[y][0])y=son[y][0];
splay(y,x);
son[y][0]=son[x][0];
f[y]=0;
f[son[x][0]]=y;
up(root=y);
val[x]-=k;
tag[x]=0;
son[x][0]=son[x][1]=0;
size[x]=1;
ins(root,x,0);
splay(x,0);
}else{
val[x]-=k;
add1(son[x][1],-k);
while(son[x][1])x=son[x][1];
val[x]=inf;
splay(x,0);
return;
}
}
}
inline int kth(int k){
int x=root,tmp;
while(1){
pb(x);
tmp=size[son[x][0]]+1;
if(k==tmp){
splay(x,0);
return val[x];
}
if(k<tmp)x=son[x][0];else k-=tmp,x=son[x][1];
}
}
int main(){
read(n),read(m);
for(i=1;i<=n;i++)read(a[i]);
a[++n]=0;
a[++n]=inf;
std::sort(a+1,a+n+1);
root=build(1,n,0);
while(m--){
read(op),read(k);
if(op==2)change(k);else printf("%d\n",kth(k+1));
}
return 0;
}
D. Eastern Subregional
留坑。
E. K-transform
DP显然，快速幂+FFT优化即可。时间复杂度$O(k\log k\log m)$。
F. Suffix Array for Thue-Morse
留坑。
G. XOR Tree
求出路径上偶数的集合然后分类讨论即可。
#include <bits/stdc++.h>
using namespace std ; typedef long long LL ; const int MAXN = 100005 ;
const int MAXE = 200005 ; struct Edge {
int v , n ;
Edge () {}
Edge ( int v , int n ) : v ( v ) , n ( n ) {}
} ; Edge E[MAXE] ;
int H[MAXN] , cntE ;
int dep[MAXN] ;
int top[MAXN] ;
int siz[MAXN] ;
int son[MAXN] ;
int pre[MAXN] ;
int pos[MAXN] ;
LL val[MAXN] ;
LL sum[MAXN] ;
int precol[MAXN] ;
int even[MAXN] ;
int tree_idx ;
int n , q ;
int eu[MAXN] , ev[MAXN] , ec[MAXN] ;
vector < int > G ;
LL all ; void init () {
cntE = 0 ;
tree_idx = 0 ;
memset ( H , -1 , sizeof H ) ;
memset ( val , 0 , sizeof val ) ;
memset ( sum , 0 , sizeof sum ) ;
memset ( even , 0 , sizeof even ) ;
} void addedge ( int u , int v ) {
E[cntE] = Edge ( v , H[u] ) ;
H[u] = cntE ++ ;
} void dfs ( int u ) {
son[u] = 0 ;
siz[u] = 1 ;
for ( int i = H[u] ; ~i ; i = E[i].n ) {
int v = E[i].v ;
if ( v == pre[u] ) continue ;
dep[v] = dep[u] + 1 ;
pre[v] = u ;
dfs ( v ) ;
siz[u] += siz[v] ;
if ( siz[son[u]] < siz[v] ) son[u] = v ;
}
} void rebuild ( int u , int top_element ) {
top[u] = top_element ;
pos[u] = ++ tree_idx ;
if ( son[u] ) rebuild ( son[u] , top_element ) ;
for ( int i = H[u] ; ~i ; i = E[i].n ) {
int v = E[i].v ;
if ( v == pre[u] || v == son[u] ) continue ;
rebuild ( v , v ) ;
}
} void dfs2 ( int u , int it ) {
precol[u] = it ;
for ( int i = H[u] ; ~i ; i = E[i].n ) {
int v = E[i].v ;
if ( v == pre[u] ) continue ;
dfs2 ( v , val[u] % 2 ? it : u ) ;
}
} void geteven ( int u , int lca ) {
//printf("geteven %d %d\n",u,lca);
while ( dep[u] > dep[lca] ) {
//printf(" %d %d %d\n",u,val[u],precol[u]);
if ( val[u] % 2 == 0 ) {
G.push_back ( val[u] ) ;
}
u = precol[u] ;
}
} void deal ( int u , int v ) {
LL tot = 0 , num = 0 ;
int x = u , y = v ;
//return;
while ( top[u] != top[v] ) {
if ( dep[top[u]] < dep[top[v]] ) swap ( u , v ) ;
num += even[pos[u]] - even[pos[top[u]] - 1] ;
tot += sum[pos[u]] - sum[pos[top[u]] - 1] ;
u = pre[top[u]] ;
}
//return;
if ( dep[u] > dep[v] ) swap ( u , v ) ;
num += even[pos[v]] - even[pos[u]] ;
tot += sum[pos[v]] - sum[pos[u]] ;
if ( num == 0 ) {
printf ( "1\n" ) ;
return ;
}
if ( num >= 3 ) {
printf ( "2\n" ) ;
return ;
}
G.clear () ;
geteven ( x , u ) ;
geteven ( y , u ) ;
int dis = dep[x] + dep[y] - 2 * dep[u] ;
sort ( G.begin () , G.end () ) ;
dis -= ( int ) G.size () ;
int out = ( all - tot ) & 1 ; // printf("->%d\n",G.size());
//return; if ( num == 1 ) {
if ( G[0] >= dis ) {
printf ( "1\n" ) ;
return ;
} else {
printf ( "2\n" ) ;
return ;
}
}
//return;
if ( num == 2 ) {
G[0] -= dis - 1 ;
if ( G[0] <= 1 ) {
printf ( "2\n" ) ;
return ;
} else {
G[0] %= 2 ;
if ( ( G[0] == 0 ) ^ ( out == 0 ) ) printf ( "2\n" ) ;
else printf ( "1\n" ) ;
return ;
}
}
} void solve () {
init () ;
all = 0 ;
for ( int i = 1 ; i < n ; ++ i ) {
scanf ( "%d%d%d" , &eu[i] , &ev[i] , &ec[i] ) ;
addedge ( eu[i] , ev[i] ) ;
addedge ( ev[i] , eu[i] ) ;
all += ec[i] ;
}
dfs ( 1 ) ;
rebuild ( 1 , 1 ) ;
for ( int i = 1 ; i < n ; ++ i ) {
if ( dep[eu[i]] > dep[ev[i]] ) {
sum[pos[eu[i]]] = ec[i] ;
val[eu[i]] = ec[i] ;
even[pos[eu[i]]] = ec[i] % 2 == 0 ;
} else {
sum[pos[ev[i]]] = ec[i] ;
val[ev[i]] = ec[i] ;
even[pos[ev[i]]] = ec[i] % 2 == 0 ;
}
}
dfs2 ( 1 , 0 ) ;
for ( int i = 2 ; i <= n ; ++ i ) {
sum[i] += sum[i - 1] ;
even[i] += even[i - 1] ;
}
while ( q -- ) {
int u , v ;
scanf ( "%d%d" , &u , &v ) ;
deal ( u , v ) ;
}
} int main () {
while ( ~scanf ( "%d%d" , &n , &q ) ) solve () ;
return 0 ;
}
H. Fence
留坑。
I. Friends and Berries - 2
首先求出凸包，然后分治求出每个点的最远点，检查一下直径是否合法，是的话那么所有直径都是答案。时间复杂度$O(n\log n)$。
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
typedef pair<int,int>PI;
const int N=500010;
int n,i,f[N];ll d[N];
map<PI,int>idx;
set<PI>ans;
struct P{
int x,y;
P(){x=y=0;}
P(int _x,int _y){x=_x,y=_y;}
void input(){scanf("%d%d",&x,&y);}
bool operator<(const P&p)const{
if(x!=p.x)return x<p.x;
return y<p.y;
}
}a[N],b[N];
inline ll dis(const P&a,const P&b){
return 1LL*(a.x-b.x)*(a.x-b.x)+1LL*(a.y-b.y)*(a.y-b.y);
}
inline ll cal(int x,int y){
ll t=dis(b[x],b[y]);
if(y<x||y>=x+n)return -t;
return t;
}
inline ll vect(P p,P p1,P p2){
return 1LL*(p1.x-p.x)*(p2.y-p.y)-1LL*(p1.y-p.y)*(p2.x-p.x);
}
int convexhull(P*p,int n,P*q){
int i,k,m;
sort(p,p+n);
m=0;
for(i=0;i<n;q[m++]=p[i++])while(m>1&&vect(q[m-2],q[m-1],p[i])<0)m--;
k=m;
for(i=n-2;i>=0;q[m++]=p[i--])while(m>k&&vect(q[m-2],q[m-1],p[i])<0)m--;
return --m;
}
void solve(int l,int r,int dl,int dr){
int m=(l+r)>>1;
f[m]=dl;
d[m]=cal(m,dl);
for(int i=dl+1;i<=dr;i++){
ll t=cal(m,i);
if(t>d[m])d[m]=t,f[m]=i;
}
if(l<m)solve(l,m-1,dl,f[m]);
if(r>m)solve(m+1,r,f[m],dr);
}
inline bool check(P A,P B){
for(int i=0;i<n;i++)if(dis(A,B)<dis(A,b[i])+dis(B,b[i]))return 0;
return 1;
}
inline void newans(int x,int y){
if(x==y)return;
if(x>y)swap(x,y);
ans.insert(PI(x,y));
}
int main(){
scanf("%d",&n);
for(i=0;i<n;i++){
a[i].input();
idx[PI(a[i].x,a[i].y)]=i+1;
}
n=convexhull(a,n,b);
if(n==2){
for(i=0;i<n;i++)printf("%d ",idx[PI(b[i].x,b[i].y)]);
return 0;
}
for(i=0;i<n;i++)b[i+n]=b[i];
solve(0,n-1,0,n*2-1);
int x=0;
for(i=1;i<n;i++)if(d[i]>d[x])x=i;
for(i=0;i<n;i++)f[i]%=n;
if(!check(b[x],b[f[x]]))return puts("0"),0;
for(i=0;i<n;i++)if(d[i]==d[x]){
//if(!check(b[i],b[f[i]))while(1);
newans(i,f[i]);
}
//for(i=0;i<n;i++)printf("%d %d\n",b[i].x,b[i].y);
//puts("");
printf("%d\n",ans.size());
for(set<PI>::iterator it=ans.begin();it!=ans.end();it++){
//printf("%d %d\n",it->first,it->second);
printf("%d %d\n",idx[PI(b[it->first].x,b[it->first].y)],
idx[PI(b[it->second].x,b[it->second].y)]);
}
}
J. Oleg and Cola
超图上的最短路，dijkstra+染色即可。时间复杂度$O(m\log m)$。
#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
typedef pair<ll,P>PI;
const int N=200010;
int n,m,i,ce,id[N],st[N][2],en[N][2];
int cnt,fin[N*2];
P pos;ll ans;
bool v[N][2];
ll d[N][2];
P pre[N][2];
priority_queue<PI,vector<PI>,greater<PI> >q;
struct E{
int u,v,len,light;
E(){}
E(int _u,int _v,int _len,int _light){u=_u,v=_v,len=_len,light=_light;}
}e[N];
inline bool cmp(int x,int y){
if(e[x].u!=e[y].u)return e[x].u<e[y].u;
return e[x].light<e[y].light;
}
inline void ext(int x,int y,ll z,P p){
if(v[x][y])return;
z+=e[x].len;
v[x][y]=1;
d[x][y]=z;
pre[x][y]=p;
q.push(PI(z,P(x,y)));
}
int main(){
scanf("%d%d",&n,&m);
for(ce=i=1;i<=m;i++){
int u,v,len,light;
scanf("%d%d%d%d",&u,&v,&len,&light);
e[++ce]=E(u,v,len,light);
e[++ce]=E(v,u,len,light);
}
for(i=2;i<=ce;i++)id[i]=i;
sort(id+2,id+ce+1,cmp);
for(i=1;i<=n;i++)st[i][0]=1;
for(i=2;i<=ce;i++)en[e[id[i]].u][0]=i;
for(i=ce;i>1;i--)st[e[id[i]].u][0]=i;
for(i=1;i<=n;i++)st[i][1]=st[i][0],en[i][1]=en[i][0];
for(i=2;i<=ce;i++)if(e[i].u==1)ext(i,0,0,P(0,0));
while(!q.empty()){
PI t=q.top();q.pop();
int x=t.second.first,y=t.second.second;
ll z=t.first;
int o=e[x].v;
while(st[o][y]<=en[o][y]){
int i=id[en[o][y]];
if(e[i].light<e[x].light)break;
ext(i,y,z,P(x,y));
en[o][y]--;
}
if(o==2&&y==0){
while(st[o][1]<=en[o][1]){
int i=id[en[o][1]];
if(e[i].light<e[x].light)break;
ext(i,1,z,P(x,y));
en[o][1]--;
}
}
}
ans=1LL<<60;
for(i=2;i<=ce;i++)if(e[i].v==1&&v[i][1]){
if(d[i][1]<ans){
ans=d[i][1];
pos=P(i,1);
}
}
printf("%lld\n",ans);
while(pos.first){
fin[++cnt]=pos.first/2;
pos=pre[pos.first][pos.second];
}
while(cnt)printf("%d ",fin[cnt--]);
}
K. Process with Constant Sum
留坑。