$\href{https://www.acwing.com/file_system/file/content/whole/index/content/8737358/}{\Huge 我的个人主页}$

6412

O₂
mortals
AlexVagrant
Jerrywang
UoU

IKUN_27

oceanrivers
hambat
Oli

liaoyanxu

oopstls
bb_8

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+1;
int n,a,b,c,s[N];
int f[N],q[N];

int x=0; bool f=true; char ch=0;
while (!isdigit(ch) ) f&=(ch!='-'),ch=getchar();
while (isdigit(ch) ) x=(x<<3)+(x<<1)+(ch&15),ch=getchar();
return f?x:-x;
}
int get(int x) {
return f[x]+a*s[x]*s[x]-b*s[x];
}
double slope(int x,int y) {
int X=get(x)-get(y),Y=s[x]-s[y];
return !X?1e30:X*1.0/Y;
}
signed main()
{
for (int i=1;i<=n;i++) s[i]=s[i-1]+read();
int hh=0,tt=0; for (int i=1;i<=n;i++)
{
while (hh<tt&&slope(q[hh+1],q[hh])>2*a*s[i]) hh++;
int p=q[hh],sum=s[i]-s[p]; f[i]=f[p]+a*sum*sum+b*sum+c;
while (hh<tt&&slope(i,q[tt])>slope(q[tt],q[tt-1]) ) tt--;
q[++tt]=i;
}
printf("%lld",f[n]);
return 0;
}


#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+1;
int d[N],a[N],s[N];
int f[2][N],q[N];
int n,m,p;

int x=0; char ch=0; while (!isdigit(ch) ) ch=getchar();
while (isdigit(ch) ) x=(x<<3)+(x<<1)+(ch&15),ch=getchar();
return x;
}
double slope(int i,int x,int y) {
return 1.0*(f[i][x]+s[x]-f[i][y]-s[y])/(x-y);
}
signed main()
{
for (int i=2;i<=n;i++) d[i]=d[i-1]+read();
sort(a+1,a+m+1); for (int i=1;i<=m;i++) s[i]=s[i-1]+a[i];
memset(f,0x3f,sizeof f); f[0][0]=f[1][0]=0;

for (int i=1;i<=p;i++)
{
int hh=0,tt=0,pre=i-1&1;
for (int j=1;j<=m;j++)
{
while (hh<tt&&slope(pre,q[hh+1],q[hh])<a[j]) hh++;
int p=q[hh]; f[i&1][j]=f[pre][p]+a[j]*(j-p)-s[j]+s[p];
while (hh<tt&&slope(pre,j,q[tt])<slope(pre,q[tt],q[tt-1]) ) tt--;
q[++tt]=j;
}
}
printf("%lld",f[p&1][m]);
return 0;
}


#include<bits/stdc++.h>
#define int long long
#define front q[hh]
#define back q[tt]
using namespace std;
const int N=5e5+1;
int n,S,t[N],c[N];
int f[N],q[N];

int x=0; char ch=0; bool f=true;
while (!isdigit(ch) ) f&=(ch!='-'),ch=getchar();
while (isdigit(ch) ) x=(x<<3)+(x<<1)+(ch&15),ch=getchar();
return f?x:-x;
}
double slope(int x,int y) { //斜率
int X=f[x]-f[y],Y=c[x]-c[y];
if (!X) return (Y>0)?1e30:-1e30;
return X*1.0/Y;
}
signed main()
{
int hh=0,tt=0; for (int i=1;i<=n;i++)
{
int l=hh,r=tt; while (l<r) { int mid=(l+r)>>1;
slope(q[mid+1],q[mid])>S+t[i]?r=mid:l=mid+1; }
int p=q[r]; f[i]=f[p]+t[i]*(c[i]-c[p])+S*(c[n]-c[p]);
while (hh<tt&&slope(i,q[tt])<slope(q[tt],q[tt-1]) ) tt--;
q[++tt]=i;
}
printf("%lld",f[n]);
return 0;
}


#include<bits/stdc++.h>
#define int long long
#define front q[hh]
#define back q[tt]
using namespace std;
const int N=3e5+1;
int n,S,t[N],c[N];
int f[N],q[N];

int x=0; char ch=0; while (!isdigit(ch) ) ch=getchar();
while (isdigit(ch) ) x=(x<<3)+(x<<1)+(ch&15),ch=getchar(); return x;
}
double slope(int x,int y) { //斜率
int X=f[x]-f[y],Y=c[x]-c[y];
if (!X) return (Y>0)?1e30:-1e30;
return X*1.0/Y;
}
signed main()
{
int hh=0,tt=0; for (int i=1;i<=n;i++)
{
while (hh<tt&&slope(q[hh+1],q[hh])<S+t[i]) hh++;
int p=q[hh]; f[i]=f[p]+t[i]*(c[i]-c[p])+S*(c[n]-c[p]);
while (hh<tt&&slope(i,q[tt])<slope(q[tt],q[tt-1]) ) tt--;
q[++tt]=i;
}
printf("%lld",f[n]);
return 0;
}


#include<bits/stdc++.h>
using namespace std;
const int N=5001;
int n,s,t[N],c[N];
long long f[N];

{
int x=0; char ch=0; while (!isdigit(ch) ) ch=getchar();
while (isdigit(ch) ) x=(x<<3)+(x<<1)+(ch&15),ch=getchar(); return x;
}
int main()
{
memset(f,0x3f,sizeof f); f[0]=0;
for (int i=1;i<=n;i++)
for (int j=0;j<i;j++)
f[i]=min(f[i],f[j]+1ll*(c[i]-c[j])*t[i]+1ll*s*(c[n]-c[j]) );
printf("%lld",f[n]);
return 0;
}


#include<bits/stdc++.h>
#define ll long long
#define mid (l+r>>1)
#define ls T[rt].l
#define rs T[rt].r
using namespace std;
const int N=4e5;
vector<int> num;
int root[N<<2];
int n,m,rp;

struct Q {
int op,l,r;
ll x;
}a[N];

struct SGT
{
int tot;
struct node {
int l,r,tag;
ll cnt;
}T[N<<7];

void push_down(int rt,int l,int r)
{
int tag=T[rt].tag; T[rt].tag=0;
if (!ls) ls=++tot; if (!rs) rs=++tot;
T[ls].tag+=tag,T[ls].cnt+=1ll*tag*(mid-l+1);
T[rs].tag+=tag,T[rs].cnt+=1ll*tag*(r-mid);
}
void modify(int &rt,int l,int r,int L,int R)
{
if (!rt) rt=++tot; if (L<=l&&r<=R) return
T[rt].tag++,T[rt].cnt+=r-l+1,void();

push_down(rt,l,r);
if (L<=mid) modify(ls,l,mid,L,R);
if (mid<R) modify(rs,mid+1,r,L,R);
T[rt].cnt=T[ls].cnt+T[rs].cnt;
}
ll query(int rt,int l,int r,int L,int R)
{
if (L<=l&&r<=R) return T[rt].cnt;

push_down(rt,l,r);
if (R<=mid) return query(ls,l,mid,L,R);
if (mid<L) return query(rs,mid+1,r,L,R);
return query(ls,l,mid,L,R)+query(rs,mid+1,r,L,R);
}
}A;

void update(int rt,int l,int r,int L,int R,int p) {
A.modify(root[rt],1,n,L,R); if (l==r) return;
p<=mid?update(rt<<1,l,mid,L,R,p):update(rt<<1|1,mid+1,r,L,R,p);
}
int Query(int rt,int l,int r,int L,int R,ll k) {
if (l==r) return l; ll cnt=A.query(root[rt<<1|1],1,n,L,R);
return k>cnt?Query(rt<<1,l,mid,L,R,k-cnt):Query(rt<<1|1,mid+1,r,L,R,k);
}
int Hash(int x) {
return lower_bound(num.begin(),num.end(),x)-num.begin();
}
int main()
{
scanf("%d%d",&n,&m); for (int i=0;i<m;i++)
scanf("%d%d%d%lld",&a[i].op,&a[i].l,&a[i].r,&a[i].x);
for (int i=0;i<m;i++) if (a[i].op==1) num.push_back(a[i].x);
sort(num.begin(),num.end() ),num.erase(unique(num.begin(),num.end() ),num.end() );

for (int i=0;i<m;i++)
{
int op=a[i].op,l=a[i].l,r=a[i].r;
if (op==1) update(1,0,num.size()-1,l,r,Hash(a[i].x) );
else printf("%d\n",num[Query(1,0,num.size()-1,l,r,a[i].x)]);
}
return 0;
}


#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1;
int n,m,ans,dis[N],a[N],q[N];
int tim,dfn[N],low[N],fa[N];
vector<int> g[N];

void cycle(int x,int y)
{
int cnt=0,hh=0,tt=-1;
for (int u=y;u^x;u=fa[u]) a[++cnt]=dis[u]; a[++cnt]=dis[x];
for (int i=1;i<=cnt;i++) a[cnt+i]=a[i]; reverse(a+1,a+2*cnt+1);

for (int i=1;i<=cnt<<1;i++)
{
while (hh<=tt&&i-q[hh]>cnt/2) hh++;
if (hh<=tt) ans=max(ans,a[i]+a[q[hh] ]+i-q[hh]);
while (hh<=tt&&a[q[tt] ]-q[tt]<a[i]-i) tt--;
q[++tt]=i;
}
for (int i=2;i<=cnt;i++)
dis[x]=max(dis[x],a[i]+min(i-1,cnt-i+1) );
}
void tarjan(int u,int f)
{
dfn[u]=low[u]=++tim;
for (int v:g[u]) if (v^f)
{
if (!dfn[v])
{
fa[v]=u; tarjan(v,u);
low[u]=min(low[u],low[v]);
if (dfn[u]<low[v]) {
ans=max(ans,dis[u]+1+dis[v]);
dis[u]=max(dis[u],dis[v]+1);
}
}
else low[u]=min(low[u],dfn[v]);
}
for (int v:g[u])
if (dfn[u]<dfn[v]&&fa[v]^u)
cycle(u,v);
}
int main()
{
scanf("%d%d",&n,&m);

while (m--)
{
int k,x,y;
scanf("%d%d",&k,&x);

while (--k)
{
scanf("%d",&y);
g[x].push_back(y);
g[y].push_back(x);
x=y;
}
}
tarjan(1,0);
printf("%d",ans);
return 0;
}


#include<bits/stdc++.h>
#define P pair<int,int>
#define v e.first
#define w e.second
using namespace std;
const int N=2e4+1; int m,q,cnt;
int n,f[N][15],depth[N],dis[N],csum[N];
int tim,dfn[N],low[N],fa[N],a[N],s[N];
vector<P> G[N],g[N];

void build_cycle(int x,int y,int z)
{
int sum=z; for (int u=y;u^x;u=fa[u])
s[u]=sum,sum+=a[u]; s[x]=csum[x]=sum;
cnt++; g[x].push_back( {cnt,0} );
for (int u=y;u^x;u=fa[u]) csum[u]=sum,
g[cnt].push_back( {u,min(s[u],sum-s[u]) } );
}
void tarjan(int u,int father)
{
dfn[u]=low[u]=++tim;
for (auto e:G[u]) if (v^father)
{
if (!dfn[v])
{
fa[v]=u,a[v]=w;
tarjan(v,u); low[u]=min(low[u],low[v]);
if (dfn[u]<low[v]) g[u].push_back( {v,w} );
}
else low[u]=min(low[u],dfn[v]);
}
for (auto e:G[u])
if (dfn[u]<dfn[v]&&fa[v]^u)
build_cycle(u,v,w);
}
void dfs(int u,int Fa) { depth[u]=depth[Fa]+1,f[u][0]=Fa;
for (int i=1;i<15;i++) f[u][i]=f[f[u][i-1] ][i-1];
for (auto e:g[u]) dis[v]=dis[u]+w,dfs(v,u);
}
int LCA(int x,int y,int &X,int &Y)
{
if (depth[x]>depth[y]) swap(x,y); for (int i=14;i>=0;i--)
if (depth[x]<=depth[f[y][i] ]) y=f[y][i]; if (x==y) return x;
for (int i=14;i>=0;i--) if (f[x][i]^f[y][i]) x=f[x][i],y=f[y][i];
X=x,Y=y; return f[x][0];
}
int main()
{
scanf("%d%d%d",&n,&m,&q);
cnt=n;

while (m--) { int x,y,z;
scanf("%d%d%d",&x,&y,&z);
G[x].push_back( {y,z} );
G[y].push_back( {x,z} );
}tarjan(1,0),dfs(1,0);

while (q--)
{
int x,y,z,X,Y; scanf("%d%d",&x,&y); z=LCA(x,y,X,Y);
if (z<=n) printf("%d\n",dis[x]+dis[y]-2*dis[z]);
else { int dx=dis[x]-dis[X],dy=dis[y]-dis[Y],t=abs(s[X]-s[Y]);
printf("%d\n",dx+dy+min(t,csum[X]-t) ); }
}
return 0;
}


#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1;
int n,m,ans,dis[N],a[N],q[N];
int tim,dfn[N],low[N],fa[N];
vector<int> g[N];

void cycle(int x,int y)
{
int cnt=0,hh=0,tt=-1;
for (int u=y;u^x;u=fa[u]) a[++cnt]=dis[u]; a[++cnt]=dis[x];
for (int i=1;i<=cnt;i++) a[cnt+i]=a[i]; reverse(a+1,a+2*cnt+1);

for (int i=1;i<=cnt<<1;i++)
{
while (hh<=tt&&i-q[hh]>cnt/2) hh++;
if (hh<=tt) ans=max(ans,a[i]+a[q[hh] ]+i-q[hh]);
while (hh<=tt&&a[q[tt] ]-q[tt]<a[i]-i) tt--;
q[++tt]=i;
}
for (int i=2;i<=cnt;i++)
dis[x]=max(dis[x],a[i]+min(i-1,cnt-i+1) );
}
void tarjan(int u,int f)
{
dfn[u]=low[u]=++tim;
for (int v:g[u]) if (v^f)
{
if (!dfn[v])
{
fa[v]=u; tarjan(v,u);
low[u]=min(low[u],low[v]);
if (dfn[u]<low[v]) {
ans=max(ans,dis[u]+1+dis[v]);
dis[u]=max(dis[u],dis[v]+1);
}
}
else low[u]=min(low[u],dfn[v]);
}
for (int v:g[u])
if (dfn[u]<dfn[v]&&fa[v]^u)
cycle(u,v);
}
int main()
{
scanf("%d%d",&n,&m);

while (m--)
{
int k,x,y;
scanf("%d%d",&k,&x);

while (--k)
{
scanf("%d",&y);
g[x].push_back(y);
g[y].push_back(x);
x=y;
}
}
tarjan(1,0);
printf("%d",ans);
return 0;
}