The 2023 CCPC Online Contest (The 2nd Universal Cup, Stage 3: Binjiang)
題解：
https://files.cnblogs.com/files/clrs97/CCPC-Online-2023-%E9%A2%98%E8%A7%A3.pdf
Code：
A. Almost Prefix Concatenation
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1000005,P=998244353,SEED1=233,MOD1=1000000007,SEED2=10007,MOD2=1000000009;
int n,m,i,j,x,v,p[N],f[N],g[N],_p[N],_f[N],_g[N],dp[N][3];char a[N],b[N];
inline void up(int&x,int y){(x+=y)>=P&&(x-=P);}
inline int cal1(int*f,int l,int r){
int t=(f[r]-1LL*f[l-1]*p[r-l+1])%MOD1;
if(t<0)t+=MOD1;
return t;
}
inline int cal2(int*f,int l,int r){
int t=(f[r]-1LL*f[l-1]*_p[r-l+1])%MOD2;
if(t<0)t+=MOD2;
return t;
}
inline int lcp(int x,int y){
int l=1,r=min(n-x,m-y)+1,t=0,mid;
while(l<=r){
mid=(l+r)>>1;
if(cal1(f,x,x+mid-1)==cal1(g,y,y+mid-1)&&cal2(_f,x,x+mid-1)==cal2(_g,y,y+mid-1))l=(t=mid)+1;else r=mid-1;
}
return t;
}
inline int query(int x){
int t=lcp(x,1);
x+=t;
if(x>n||t==m)return x;
x++;
return x+lcp(x,t+2);
}
int main(){
scanf("%s%s",a+1,b+1);
n=strlen(a+1),m=strlen(b+1);
for(p[0]=i=1;i<=n||i<=m;i++)p[i]=1LL*p[i-1]*SEED1%MOD1;
for(i=1;i<=n;i++)f[i]=(1LL*f[i-1]*SEED1+a[i])%MOD1;
for(i=1;i<=m;i++)g[i]=(1LL*g[i-1]*SEED1+b[i])%MOD1;
for(_p[0]=i=1;i<=n||i<=m;i++)_p[i]=1LL*_p[i-1]*SEED2%MOD2;
for(i=1;i<=n;i++)_f[i]=(1LL*_f[i-1]*SEED2+a[i])%MOD2;
for(i=1;i<=m;i++)_g[i]=(1LL*_g[i-1]*SEED2+b[i])%MOD2;
dp[0][0]=1;
dp[1][0]=P-1;
for(i=0;i<=n;i++){
if(i)for(j=0;j<3;j++)up(dp[i][j],dp[i-1][j]);
if(i<n){
x=query(i+1);
for(j=0;j<3;j++){
v=dp[i][j];
if(!v)continue;
up(dp[i+1][j],v);
up(dp[x][j],P-v);
if(j<2){
up(dp[i+1][j+1],v);
up(dp[x][j+1],P-v);
}
}
}
}
printf("%d\n",((dp[n][2]*2LL+dp[n][1])%P+P)%P);
}
B. Palindromic Beads
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=200005,K=19,M=N/2*K*K+5;
int n,i,x,y,z,dp,ans,A,B,C,D,col[N],g[N],v[N<<1],nxt[N<<1],ed;
int f[N],d[N],size[N],son[N],top[N],st[N],en[N],dfn;
int T[524295],l[M],r[M],val[M],tot;
struct E{
int u,v,len;
void ext(int x){if(!u)u=x;else v=x;}
}e[N];
inline bool cmp(const E&a,const E&b){return a.len>b.len;}
inline void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}
void dfs(int x,int y){
f[x]=y;
d[x]=d[y]+1;
size[x]=1;
for(int i=g[x];i;i=nxt[i]){
int u=v[i];
if(u==y)continue;
dfs(u,x);
size[x]+=size[u];
if(size[u]>size[son[x]])son[x]=u;
}
}
void dfs2(int x,int y){
top[x]=y;
st[x]=++dfn;
if(son[x])dfs2(son[x],y);
for(int i=g[x];i;i=nxt[i]){
int u=v[i];
if(u==f[x]||u==son[x])continue;
dfs2(u,u);
}
en[x]=dfn;
}
inline int lca(int x,int y){
for(;top[x]!=top[y];x=f[top[x]])if(d[top[x]]<d[top[y]])swap(x,y);
return d[x]<d[y]?x:y;
}
inline bool sub(int x,int y){return st[x]<=st[y]&&en[y]<=en[x];}
inline int find(int x,int y){
for(int i=g[x];i;i=nxt[i]){
int u=v[i];
if(u==f[x])continue;
if(sub(u,y))return u;
}
return 0;
}
inline void up(int&a,int b){a<b?(a=b):0;}
void INS(int&x,int a,int b){
if(!x)x=++tot;
up(val[x],dp);
if(a==b)return;
int mid=(a+b)>>1;
if(C<=mid)INS(l[x],a,mid);else INS(r[x],mid+1,b);
}
void ASK(int x,int a,int b){
if(!x)return;
if(C<=a&&b<=D){up(dp,val[x]);return;}
int mid=(a+b)>>1;
if(C<=mid)ASK(l[x],a,mid);
if(D>mid)ASK(r[x],mid+1,b);
}
void ins(int x,int a,int b){
INS(T[x],1,n);
if(a==b)return;
int mid=(a+b)>>1;
if(A<=mid)ins(x<<1,a,mid);else ins(x<<1|1,mid+1,b);
}
void ask(int x,int a,int b){
if(A<=a&&b<=B){ASK(T[x],1,n);return;}
int mid=(a+b)>>1;
if(A<=mid)ask(x<<1,a,mid);
if(B>mid)ask(x<<1|1,mid+1,b);
}
int main(){
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d",&col[i]);
e[col[i]].ext(i);
}
for(i=1;i<n;i++)scanf("%d%d",&x,&y),add(x,y),add(y,x);
dfs(1,0);
dfs2(1,1);
for(i=1;i<=n;i++){
x=e[i].u,y=e[i].v;
if(!y)continue;
e[i].len=d[x]+d[y]-2*d[lca(x,y)];
}
sort(e+1,e+n+1,cmp);
ans=1;
for(i=1;i<=n;i++){
x=e[i].u,y=e[i].v;
if(!y)continue;
if(st[x]>st[y])swap(x,y);
dp=0;
if(sub(x,y)){
z=find(x,y);
A=1,B=st[z]-1,C=st[y],D=en[y];
if(A<=B)ask(1,1,n);
A=st[y],B=en[y],C=en[z]+1,D=n;
if(C<=D)ask(1,1,n);
}else{
A=st[x],B=en[x],C=st[y],D=en[y];
ask(1,1,n);
}
up(ans,dp+=2);
if(e[i].len>1)up(ans,dp+1);
A=st[x],C=st[y];
ins(1,1,n);
}
printf("%d",ans);
}
C. Clique Challenge
#include<cstdio>
const int N=1005,P=1000000007,K=23;
int n,m,i,j,x,y,d[N],q[N];long long ans;
int left,full,gl[K],gr[K],ban[K],f[(1<<K)+1];
bool g[N][N];
void dfs(int x,int S,int T){
if(x==left){
ans+=f[full^T];
return;
}
dfs(x+1,S,T);
if(!(S&gl[x]))dfs(x+1,S^(1<<x),T|ban[x]);
}
inline void solve(){
if(m<=1){
ans+=m+1;
return;
}
left=m/2;
full=(1<<(m-left))-1;
int i,j;
for(i=0;i<left;i++){
gl[i]=ban[i]=0;
for(j=0;j<left;j++)if(i!=j&&!g[q[i]][q[j]])gl[i]|=1<<j;
for(j=left;j<m;j++)if(!g[q[i]][q[j]])ban[i]|=1<<(j-left);
}
for(i=left;i<m;i++){
gr[i-left]=0;
for(j=left;j<m;j++)if(i!=j&&!g[q[i]][q[j]])gr[i-left]|=1<<(j-left);
}
f[0]=1;
for(int S=1;S<=full;S++){
int T=S^(S&-S);
f[S]=f[T]+f[T^(S&gr[__builtin_ctz(S)])];
}
dfs(0,0,0);
}
int main(){
scanf("%d%d",&n,&m);
while(m--){
scanf("%d%d",&x,&y);
g[x][y]=g[y][x]=1;
d[x]++,d[y]++;
}
for(i=1;i<=n;i++){
m=0;
for(j=1;j<i;j++)if(g[i][j]&&d[j]>d[i])q[m++]=j;
for(j=i+1;j<=n;j++)if(g[i][j]&&d[j]>=d[i])q[m++]=j;
solve();//can empty
}
printf("%lld",ans%P);
}
D. Discrete Fourier Transform
#include<bits/stdc++.h>
using namespace std;
typedef long double db;
const int MAXN=2005;
const db PI=acos(-1.0);
complex<db> w[MAXN],b[MAXN];
db cal(int n,int k,int x)
{
db res=0;
for(int i=0;i<n;i++)
res=max(res,abs(b[i]+w[i*k%n]*complex<db>(x,0)));
return res;
}
int a[MAXN];
int main()
{
int n,k;
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
for(int i=0;i<n;i++)
w[i].real(cos(-2*PI/n*i)),w[i].imag(sin(-2*PI/n*i));
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
b[i]+=w[i*j%n]*complex<db>(a[j],0);
int l=-MAXN*2000,r=MAXN*2000;
while(l<r)
{
int m1=l+(r-l)/3,m2=l+2*(r-l+1)/3;
if(cal(n,k,m1)>cal(n,k,m2))l=m1+1;
else r=m2-1;
}
return 0*printf("%.18Lf\n",cal(n,k,l));
}
E. Robot Experiment
#include<cstdio>
const int N=25;
int n,ans,i,j,f[N*2][N*2];bool v[N*2][N*2];char s[N];
void dfs(int o,int x,int y){
if(o==n){
if(!v[x][y])ans++,v[x][y]=1;
return;
}
int nx=x,ny=y;
if(s[o]=='L')nx--;
if(s[o]=='R')nx++;
if(s[o]=='D')ny--;
if(s[o]=='U')ny++;
for(int i=-1;i<=1;i+=2){
if(f[nx][ny]&&f[nx][ny]!=i)continue;
int t=f[nx][ny];
f[nx][ny]=i;
dfs(o+1,i==1?nx:x,i==1?ny:y);
f[nx][ny]=t;
}
}
int main(){
scanf("%d%s",&n,s);
f[N][N]=1;
dfs(0,N,N);
printf("%d\n",ans);
for(i=0;i<N*2;i++)for(j=0;j<N*2;j++)if(v[i][j])printf("%d %d\n",i-N,j-N);
}
F. Flying Ship Story
#include<bits/stdc++.h>
using namespace std;
int q,op,x,y,w,i,j,ans,n,m;
struct E{int x,y,w;}e[9],f[9];
int S,lx,ly,vx,vy;
/*
0: x? ?y
1: x?
2: ?y
3: xy xy
4: xy
5: none
*/
inline bool ext(const E&e){
if(S==5)return 0;
if(!m){
S=0;
lx=e.x,ly=e.y;
return 1;
}
if(S==0){
if(lx==e.x&&ly==e.y)return 0;
if(lx!=e.x&&ly!=e.y){
S=3;
vx=e.x,vy=ly;
ly=e.y;
return 1;
}
if(lx==e.x){
S=1;
return 1;
}
S=2;
return 1;
}
if(S==1){
if(lx==e.x)return 0;
S=4;
ly=e.y;
return 1;
}
if(S==2){
if(ly==e.y)return 0;
S=4;
lx=e.x;
return 1;
}
bool A=lx!=e.x&&ly!=e.y,B=vx!=e.x&&vy!=e.y;
if(S==3){
if(!A&&!B)return 0;
if(A&&B){
S=5;
return 1;
}
S=4;
if(A)lx=vx,ly=vy;
return 1;
}
if(A){
S=5;
return 1;
}
return 0;
}
int main(){
scanf("%d",&q);
while(q--){
scanf("%d%d%d",&op,&x,&y);x^=ans,y^=ans;
if(op==1){
scanf("%d",&w);w^=ans;
for(i=0;i<n;i++)if(e[i].w<w)break;
for(j=n;j>i;j--)e[j]=e[j-1];
n++;
e[i].x=x;
e[i].y=y;
e[i].w=w;
for(i=m=S=0;i<n;i++)if(ext(e[i]))f[m++]=e[i];
for(i=0,n=m;i<n;i++)e[i]=f[i];
}else{
ans=0;
for(i=0;i<n;i++)if(e[i].x!=x&&e[i].y!=y){
ans=e[i].w;
break;
}
printf("%d\n",ans);
}
}
}
G. GCD of Pattern Matching
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxc = 26, maxl = 16;
void solve() {
int d;
static char buf[maxl + 1];
scanf("%d%s", &d, buf);
int len = strlen(buf), m = 0;
static int st = 0, tim[maxc + 1] = {}, idx[maxc + 1];
static LL coeff[maxl + 1];
if(!(++st)) {
memset(tim, 0, sizeof tim);
++st;
}
LL pw = 1;
for(int i = len - 1; i >= 0; --i, pw *= d) {
int o = buf[i] - 'a';
if(tim[o] != st) {
tim[o] = st;
idx[o] = m;
coeff[m++] = 0;
}
coeff[idx[o]] += pw;
}
int fir = idx[buf[0] - 'a'];
LL com = coeff[fir];
for(int i = 0, p = 0; i < m; ++i) {
if(i == fir)
continue;
if(!p) {
p = 2;
continue;
}
com += coeff[i] * (p++);
}
if(d == 2) {
printf("%lld\n", com);
return;
}
if(m < d)
coeff[m++] = 0;
for(int i = 1; i < m; ++i)
com = gcd(com, abs(coeff[i - 1] - coeff[i]));
printf("%lld\n", com);
}
int main() {
int T = 1;
scanf("%d", &T);
for(int Case = 1; Case <= T; ++Case) {
// printf("Case %d: ", Case);
solve();
}
return 0;
}
H. Hurricane
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=100005;
const int INF=0x3f3f3f3f;
vector<int> e[MAXN];
int dis[MAXN];
bool ban[MAXN];
void bfs(int s,int n)
{
fill(dis+1,dis+n+1,INF);
dis[s]=0;
queue<int,list<int>> que;
que.push(s);
list<int> lst;
for(int i=1;i<=n;i++)
lst.push_back(i);
while(!que.empty())
{
int u=que.front();
que.pop();
for(auto v : e[u])
ban[v]=1;
for(auto itr=lst.begin();itr!=lst.end();)
{
int v=*itr;
if(ban[v])
{
++itr;
continue;
}
if(dis[v]>dis[u]+1)
{
dis[v]=dis[u]+1;
que.push(v);
}
lst.erase(itr++);
}
for(auto v : e[u])
ban[v]=0;
}
}
int deg[MAXN],idx[MAXN],ord[MAXN];
ll res[MAXN];
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
e[u].push_back(v);
e[v].push_back(u);
++deg[u],++deg[v];
}
iota(idx+1,idx+n+1,1);
sort(idx+1,idx+n+1,[](int x,int y)
{
return deg[x]>deg[y];
});
for(int i=1;i<=n;i++)
ord[idx[i]]=i;
int b;
for(b=1;b<=n && 2*deg[idx[b]]>=n;b++)
{
bfs(idx[b],n);
for(int i=1;i<=n;i++)
if(ord[i]>b && dis[i]<n)
++res[dis[i]];
}
res[1]+=1LL*(n+1-b)*(n-b)/2;
for(;b<=n;b++)
for(auto v : e[idx[b]])
if(ord[v]>b)
--res[1],++res[2];
for(int i=1;i<=n-1;i++)
printf("%lld%c",res[i]," \n"[i==n-1]);
return 0;
}
I. Monster Generator
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=205;
int n,m,i,j,day,e[N*N],id[N],st[N],en[N];unsigned long long ans;
struct Mon{
ll ia,ib,da,db;
void read(){scanf("%lld%lld%lld%lld",&ia,&da,&ib,&db);}
}mon[N];
struct P{
lll a,b;int sgn;
P(){}
P(lll _a,lll _b){
a=_a;
b=_b;
if(a<b)sgn=1;else if(a==b)sgn=0;else sgn=-1;
}
int cmp(const P&o)const{
if(sgn!=o.sgn)return sgn>o.sgn?-1:1;
if(a==b)return 0;
if(a<b){
if(a==o.a)return 0;
return a<o.a?-1:1;
}
if(b==o.b)return 0;
return b>o.b?-1:1;
}
}vl[N],vr[N];
inline bool cmpid(int x,int y){
int t=vl[x].cmp(vl[y]);
if(t)return t<0;
return vr[x].cmp(vr[y])<0;
}
struct Line{ll k,b;}line[N],hull[N];
inline bool cmpline(const Line&a,const Line&b){
if(a.k!=b.k)return a.k<b.k;
return a.b>b.b;
}
inline void cal(const Line&p,ll l,ll r){
if(l>r)return;
//printf("l=%lld r=%lld k=%lld b=%lld\n",l,r,p.k,p.b);
ans+=(l+r)*(r-l+1)/2*p.k+p.b*(r-l+1);
}
inline void solve(int l,int r){
if(l>r)return;
//printf("[%d,%d]\n",l,r);
int i;
for(i=1;i<=n;i++){
id[i]=i;
vl[i]=P(mon[i].ia+mon[i].da*l,mon[i].ib+mon[i].db*l);
vr[i]=P(mon[i].ia+mon[i].da*r,mon[i].ib+mon[i].db*r);
}
sort(id+1,id+n+1,cmpid);
ll sumk=0,sumb=0;
line[0].k=line[0].b=0;
for(i=1;i<=n;i++){
int o=id[i];
sumk+=mon[o].da;
sumb+=mon[o].ia;
line[i].k=sumk;
line[i].b=sumb;
sumk-=mon[o].db;
sumb-=mon[o].ib;
}
//sum max
sort(line,line+n+1,cmpline);
int t=0;
for(i=0;i<=n;i++)if(!i||line[i].k>line[i-1].k){
//printf("ext %lld %lld\n",line[i].k,line[i].b);
while(t>1&&(hull[t-1].b-hull[t].b)*(line[i].k-hull[t].k)>=(hull[t].b-line[i].b)*(hull[t].k-hull[t-1].k))t--;
hull[++t]=line[i];
}
for(i=1;i<=t;i++)st[i]=l,en[i]=r;
for(i=1;i<t;i++){
ll u=hull[i].b-hull[i+1].b,d=hull[i+1].k-hull[i].k;
if(u<0){
en[i]=-1;
continue;
}
u/=d;
//printf("i=%d u=%lld\n",i,u);
if(u<en[i])en[i]=u;
u++;
if(u>r)st[i+1]=r+1;
else if(u>st[i+1])st[i+1]=u;
}
for(i=1;i<=t;i++)cal(hull[i],st[i],en[i]);
}
inline void split(ll b1,ll k1,ll b2,ll k2){
if(k1==k2)return;
ll u=b2-b1,d=k1-k2;
if(d<0)u*=-1,d*=-1;
//d>0
if(u<=0)return;
//u>0
u/=d;
//<=u >u
if(u>=day)return;
e[++m]=u;
}
int main(){
scanf("%d%d",&n,&day);//[0..day]
for(i=1;i<=n;i++){
mon[i].read();
split(mon[i].ia,mon[i].da,mon[i].ib,mon[i].db);
}
for(i=1;i<=n;i++)for(j=1;j<i;j++){
split(mon[i].ia,mon[i].da,mon[j].ia,mon[j].da);
split(mon[i].ib,mon[i].db,mon[j].ib,mon[j].db);
}
e[++m]=-1;
e[++m]=day;
sort(e+1,e+m+1);
for(i=2;i<=m;i++)solve(e[i-1]+1,e[i]);
printf("%llu",ans);
}
J. Find the Gap
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll inf=~0ULL>>1;
const int N=55;
int n,m,i,j,k,flag;ld ans;
struct P{
ll x,y,z;
P(){}
P(ll _x,ll _y,ll _z){x=_x,y=_y,z=_z;}
void read(){scanf("%lld%lld%lld",&x,&y,&z);}
ll len(){return x*x+y*y+z*z;}
ll operator^(const P&b){return x*b.x+y*b.y+z*b.z;}
P operator-(const P&b)const{return P(x-b.x,y-b.y,z-b.z);}
P operator*(const P&b)const{return P(y*b.z-z*b.y,z*b.x-x*b.z,x*b.y-y*b.x);}
}v[N],l[N*N/2];
int main(){
scanf("%d",&n);
for(i=0;i<n;i++)v[i].read();
for(i=0;i<n;i++)for(j=0;j<i;j++)l[m++]=v[i]-v[j];
ans=1e100;
for(i=0;i<m;i++)for(j=0;j<i;j++){
P f=l[i]*l[j];
ll len=f.len();
if(!len)continue;
flag=1;
ll mi=inf,ma=-inf;
for(k=0;k<n;k++){
ll tmp=f^v[k];
if(tmp<mi)mi=tmp;
if(tmp>ma)ma=tmp;
}
ld now=((ld)(ma-mi))/sqrtl(len);
if(ans>now)ans=now;
}
if(!flag)ans=0;
printf("%.15f",(double)ans);
}
K. Sequence Shift
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef pair<int,int>P;
typedef long double ld;
const int N=3000005,W=1000000000;
int n,q,m,k,i,v,a[N],b[N],lim,f[N];P p[N];
inline void ext(int x,int v){
b[x]=v;
for(int i=1;i<=n;i++){
int now=p[i].first+v;
if(now<lim)break;
int pos=n+x-p[i].second;
if(pos<n||pos>m)continue;
if(f[pos]<now)f[pos]=now;
}
}
inline int cal(int x){
if(f[x])return f[x];
int ret=0;
for(int i=1;i<=n;i++){
int now=a[i]+b[x-n+i];
if(now>ret)ret=now;
}
return f[x]=ret;
}
int main(){
scanf("%d%d",&n,&q);
m=n+q;
ld best=(1.0-powl((ld)m/(ld)n/((ld)(m-n+1)),1.0/((ld)(n-1))))*((ld)n)*((ld)m)*2.0*((ld)n)*((ld)m)/((ld)(n+m))/((ld)(n+m));
ld bestk=sqrtl(max(best,(ld)0.0));
k=bestk;
k=min(max(k,1),n);
for(i=1;i<=n;i++){
scanf("%d",&a[i]);
p[i]=P(a[i],i);
}
sort(p+1,p+n+1);
reverse(p+1,p+n+1);
lim=p[k].first+((ld)(m-k+1))*((ld)W)/((ld)m);
for(i=1;i<=m;i++){
scanf("%d",&v);
if(i>n)v^=f[i-1];
ext(i,v);
if(i>=n)printf("%d\n",cal(i));
}
}
L. Partially Free Meal
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=200005,M=N*20;
int n,i,tot,v[N],T[N],l[M],r[M],cnt[M];ll sum[M],f[N];
struct E{int a,b;}e[N];
inline bool cmp(const E&a,const E&b){return a.b<b.b;}
int ins(int x,int a,int b,int c,int p){
int y=++tot;
cnt[y]=cnt[x]+1;
sum[y]=sum[x]+p;
if(a==b)return y;
int mid=(a+b)>>1;
if(c<=mid)l[y]=ins(l[x],a,mid,c,p),r[y]=r[x];
else l[y]=l[x],r[y]=ins(r[x],mid+1,b,c,p);
return y;
}
inline ll kth(int x,int k){
ll ret=0;
int a=1,b=n,mid,t;
while(a<b){
mid=(a+b)>>1;
t=cnt[l[x]];
if(k<=t){
x=l[x];
b=mid;
}else{
k-=t;
ret+=sum[l[x]];
x=r[x];
a=mid+1;
}
}
return ret+1LL*k*v[a];
}
inline ll ask(int x,int k){
ll ret=e[x].a+e[x].b;
if(k>1)ret+=kth(T[x-1],k-1);
return ret;
}
void solve(int l,int r,int dl,int dr){
int m=(l+r)>>1,dm=0;
ll best;
for(int i=dr;i>=dl&&i>=m;i--){
ll now=ask(i,m);
if(!dm||now<best)best=now,dm=i;
}
f[m]=best;
if(l<m)solve(l,m-1,dl,dm);
if(r>m)solve(m+1,r,dm,dr);
}
int main(){
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d%d",&e[i].a,&e[i].b);
v[i]=e[i].a;
}
sort(v+1,v+n+1);
sort(e+1,e+n+1,cmp);
for(i=1;i<=n;i++)T[i]=ins(T[i-1],1,n,lower_bound(v+1,v+n+1,e[i].a)-v,e[i].a);
solve(1,n,1,n);
for(i=1;i<=n;i++)printf("%lld\n",f[i]);
}
浙公網安備 33010602011771號