6
19
2016
0

[BZOJ3083] 遥远的国度

和我做过的另外一个BZOJ题很像,但是忘了题号了……BZOJ3306 题解

换根就是针对当前根找到子树然后容斥一下

注意dfs序中一棵树的子树一定是连续的

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
 
const int N=100005;
 
int n,m,a[N],id[N],pre[N],segn,en,h[N],root,siz[N],son[N],dep[N],fa[N],top[N],OPTION;
 
struct Edge{
int b,next;
}e[N<<1];
 
void AddEdge(int sa,int sb){
e[++en].b=sb;
e[en].next=h[sa];
h[sa]=en;
}
 
struct SegTree{
int l,r,mn,tag;
}tree[N<<2];
 
void Pushdown(int rt){
if(tree[rt].tag){
    tree[rt<<1].tag=tree[rt].tag;
    tree[rt<<1|1].tag=tree[rt].tag;
    tree[rt<<1].mn=tree[rt].tag;
    tree[rt<<1|1].mn=tree[rt].tag;
    tree[rt].tag=0;
}
}
 
void Pushup(int rt){
tree[rt].mn=min(tree[rt<<1].mn,tree[rt<<1|1].mn);
}
 
void Build(int rt,int l,int r){
tree[rt].l=l;tree[rt].r=r;
if(l==r){tree[rt].mn=a[pre[l]];return;}
int mid=l+r>>1;
Build(rt<<1,l,mid);
Build(rt<<1|1,mid+1,r);
Pushup(rt);
}
 
void Modify(int rt,int l,int r,int x){
if(l<=tree[rt].l && tree[rt].r<=r){tree[rt].mn=x;tree[rt].tag=x;return;}
Pushdown(rt);
int mid=tree[rt].l+tree[rt].r>>1;
if(l<=mid)Modify(rt<<1,l,r,x);
if(r>mid)Modify(rt<<1|1,l,r,x);
Pushup(rt);
}
 
int Query(int rt,int l,int r){
if(l<=tree[rt].l && tree[rt].r<=r)return tree[rt].mn;
Pushdown(rt);
int mid=tree[rt].l+tree[rt].r>>1;
if(r<=mid)return Query(rt<<1,l,r);
else if(l>mid)return Query(rt<<1|1,l,r);
else return min(Query(rt<<1,l,r),Query(rt<<1|1,l,r));
}
 
void dfs1(int u,int fat){
siz[u]=1;
dep[u]=dep[fat]+1;
son[u]=0;
fa[u]=fat;
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v==fat)continue;
    dfs1(v,u);
    siz[u]+=siz[v];
    if(siz[v]>siz[son[u]])son[u]=v;
}
}
 
void dfs2(int u,int ux){
top[u]=ux;
id[u]=++segn;
pre[segn]=u;
if(son[u])dfs2(son[u],ux);
else return;
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(son[u]==v || fa[u]==v)continue;
    dfs2(v,v);
}
}
 
void Change(int x,int y,int v){
int topx=top[x],topy=top[y];
while(topx!=topy){
    if(dep[topx]<dep[topy]){swap(topx,topy);swap(x,y);}
    Modify(1,id[topx],id[x],v);
    x=fa[topx];
    topx=top[x];
}
if(dep[x]>dep[y])swap(x,y);
Modify(1,id[x],id[y],v);
}
 
int Ask(int Id){
if(root==Id)return Query(1,1,n);
int x=root,y=Id,topx=top[x],topy=top[y];
while(topx!=topy){
    if(dep[topx]<dep[topy]){swap(topx,topy);swap(x,y);}
    x=fa[topx];
    topx=top[x];
}
if(dep[x]>dep[y])swap(x,y);
if(x!=Id)return Query(1,id[Id],id[Id]+siz[Id]-1);
else {
    for(int i=h[Id];i;i=e[i].next){
        int v=e[i].b;
        if(fa[Id]==v)continue;
        if(id[v]<=id[root] && id[root]<=id[v]+siz[v]-1){
            int mn=Query(1,id[1],id[v]-1);
            if(id[v]+siz[v]-1!=n)mn=min(mn,Query(1,id[v]+siz[v],n));
            return mn;
        }
    }
}
}
 
void Read(int &x){
char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=x*10+ch-'0';
}
 
int main(){
freopen("3083.in","r",stdin);
freopen("3083.out","w",stdout);
Read(n);Read(m);
for(int i=1;i<n;i++){int u,v;Read(u);Read(v);AddEdge(u,v);AddEdge(v,u);}
for(int i=1;i<=n;i++)Read(a[i]);
Read(root);
dfs1(1,0);
dfs2(1,1);
Build(1,1,n);
while(m--){
    int opt,x,y,v;
    Read(opt);
    if(opt==1){Read(x);root=x;}
    if(opt==2){Read(x);Read(y);Read(v);Change(x,y,v);}
    if(opt==3){Read(x);printf("%d\n",Ask(x));}
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
6
19
2016
0

[BZOJ3732] Network

最小生成树弄出来倍增就没了

和NOIP的货车运输没什么区别

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
 
const int N=15005;
 
int n,m,f[N],k,cnt,dep[N],fa[N][15],V[N][15],en,h[N];
 
struct Ed{
int a,b,v;
friend bool operator<(Ed A,Ed B){return A.v<B.v;}
}es[N<<1];
 
struct Edge{
int b,v,next;
}e[N<<1];
 
void AddEdge(int sa,int sb,int sc){
e[++en].b=sb;
e[en].v=sc;
e[en].next=h[sa];
h[sa]=en;
}
 
int Find(int x){return x==f[x]?x:f[x]=Find(f[x]);}
 
int LCA(int u,int v){
if(dep[u]<dep[v])swap(u,v);
int deep=dep[u]-dep[v],Mx=-1;
for(int i=0;i<=14;i++)if(deep&(1<<i)){Mx=max(Mx,V[u][i]);u=fa[u][i];}
for(int i=14;i>=0;i--){
    if(fa[u][i]!=fa[v][i]){Mx=max(Mx,max(V[u][i],V[v][i]));u=fa[u][i];v=fa[v][i];}
}
return u==v?Mx:max(Mx,max(V[u][0],V[v][0]));
}
 
void Prepare(){
for(int i=1;i<=14;i++){
    for(int j=1;j<=n;j++){
        fa[j][i]=fa[fa[j][i-1]][i-1];
        V[j][i]=max(V[j][i-1],V[fa[j][i-1]][i-1]);
    }
}
}
 
void dfs(int u,int fat){
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v==fat)continue;
    fa[v][0]=u;
    dep[v]=dep[u]+1;
    V[v][0]=e[i].v;
    dfs(v,u);
}
}
 
int main(){
freopen("3732.in","r",stdin);
freopen("3732.out","w",stdout);
scanf("%d %d %d",&n,&m,&k);
for(int i=1;i<=n;i++)f[i]=i;
for(int i=1;i<=m;i++)scanf("%d %d %d",&es[i].a,&es[i].b,&es[i].v);
sort(es+1,es+m+1);
for(int i=1;i<=m && cnt<n-1;i++){
    if(Find(es[i].a)!=Find(es[i].b)){
        AddEdge(es[i].a,es[i].b,es[i].v);
        AddEdge(es[i].b,es[i].a,es[i].v);
        cnt++;
        f[Find(es[i].a)]=Find(es[i].b);
    }
}
dfs(1,0);
Prepare();
for(int i=1;i<=k;i++){
    int u,v;
    scanf("%d %d",&u,&v);
    printf("%d\n",LCA(u,v));
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
6
19
2016
0

[BZOJ4127] Abs

嗯……

因为每次加上的d都是正值,那么最多只有n次从负数到非负数的转换

所以我们分正负数分别维护,统计贡献时加一加就好了

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;
 
const int N=100005;
const long long INF=999999999999999ll;
 
int n,m,dep[N],siz[N],son[N],fa[N],id[N],pre[N],segn,en,h[N],top[N];
long long a[N];
 
struct Edge{
int b,next;
}e[N<<1];
 
void AddEdge(int sa,int sb){e[++en].b=sb;e[en].next=h[sa];h[sa]=en;}
 
struct SegTree{
int l,r;
long long s1,s2,tag,mx,sn1,sn2,sum;
}tree[N<<2];
 
void Pushdown(int rt){
if(tree[rt].tag){
    tree[rt<<1].tag+=tree[rt].tag;
    tree[rt<<1].s1+=tree[rt<<1].sn1*tree[rt].tag;
    tree[rt<<1].s2+=tree[rt<<1].sn2*tree[rt].tag;
    tree[rt<<1].sum=tree[rt<<1].s1-tree[rt<<1].s2;
    tree[rt<<1].mx+=tree[rt].tag;
    tree[rt<<1|1].tag+=tree[rt].tag;
    tree[rt<<1|1].s1+=tree[rt<<1|1].sn1*tree[rt].tag;
    tree[rt<<1|1].s2+=tree[rt<<1|1].sn2*tree[rt].tag;
    tree[rt<<1|1].sum=tree[rt<<1|1].s1-tree[rt<<1|1].s2;
    tree[rt<<1|1].mx+=tree[rt].tag;
    tree[rt].tag=0;
}
}
 
void Pushup(int rt){
tree[rt].mx=max(tree[rt<<1].mx,tree[rt<<1|1].mx);
tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;
tree[rt].sn1=tree[rt<<1].sn1+tree[rt<<1|1].sn1;
tree[rt].sn2=tree[rt<<1].sn2+tree[rt<<1|1].sn2;
tree[rt].s1=tree[rt<<1].s1+tree[rt<<1|1].s1;
tree[rt].s2=tree[rt<<1].s2+tree[rt<<1|1].s2;
}
 
void Build(int rt,int l,int r){
tree[rt].l=l;tree[rt].r=r;
if(l==r){
    if(a[pre[l]]>=0){
        tree[rt].s1+=a[pre[l]];
        tree[rt].sn1=1;
        tree[rt].mx=-INF;
    }
    else {
        tree[rt].s2+=a[pre[l]];
        tree[rt].sn2=1;
        tree[rt].mx=a[pre[l]];
    }
    tree[rt].sum=tree[rt].s1-tree[rt].s2;
    return;
}
int mid=l+r>>1;
Build(rt<<1,l,mid);
Build(rt<<1|1,mid+1,r);
Pushup(rt);
}
 
void Ex_Modify(int rt,int d){
if(tree[rt].l==tree[rt].r){
    tree[rt].sn1=1;
    tree[rt].sn2=0;
    tree[rt].s1=tree[rt].s2+d;
    tree[rt].s2=0;
    tree[rt].mx=-INF;
    tree[rt].sum=tree[rt].s1;
    return;
}
Pushdown(rt);
if(tree[rt<<1].mx+d>0)Ex_Modify(rt<<1,d);
else {
    tree[rt<<1].tag+=d;
    tree[rt<<1].s1+=tree[rt<<1].sn1*d;
    tree[rt<<1].s2+=tree[rt<<1].sn2*d;
    tree[rt<<1].sum=tree[rt<<1].s1-tree[rt<<1].s2;
    tree[rt<<1].mx+=d;
}
if(tree[rt<<1|1].mx+d>0)Ex_Modify(rt<<1|1,d);
else {
    tree[rt<<1|1].tag+=d;
    tree[rt<<1|1].s1+=tree[rt<<1|1].sn1*d;
    tree[rt<<1|1].s2+=tree[rt<<1|1].sn2*d;
    tree[rt<<1|1].sum=tree[rt<<1|1].s1-tree[rt<<1|1].s2;
    tree[rt<<1|1].mx+=d;
}
Pushup(rt);
}
 
void Modify(int rt,int l,int r,long long d){
if(l<=tree[rt].l && tree[rt].r<=r){
    if(tree[rt].mx+d>0){Ex_Modify(rt,d);}
    else {tree[rt].tag+=d;tree[rt].mx+=d;tree[rt].s1+=d*tree[rt].sn1;tree[rt].s2+=d*tree[rt].sn2;tree[rt].sum=tree[rt].s1-tree[rt].s2;}
    return;
}
Pushdown(rt);
int mid=tree[rt].l+tree[rt].r>>1;
if(l<=mid)Modify(rt<<1,l,r,d);
if(r>mid)Modify(rt<<1|1,l,r,d);
Pushup(rt);
}
 
long long Query(int rt,int l,int r){
if(l<=tree[rt].l && tree[rt].r<=r)return tree[rt].sum;
Pushdown(rt);
int mid=tree[rt].l+tree[rt].r>>1;
if(r<=mid)return Query(rt<<1,l,r);
else if(l>mid)return Query(rt<<1|1,l,r);
else return Query(rt<<1,l,r)+Query(rt<<1|1,l,r);
}
 
void dfs1(int u,int fat){
dep[u]=dep[fat]+1;
fa[u]=fat;
siz[u]=1;
son[u]=0;
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v==fat)continue;
    dfs1(v,u);
    siz[u]+=siz[v];
    if(siz[v]>siz[son[u]])son[u]=v;
}
}
 
void dfs2(int u,int ux){
top[u]=ux;
id[u]=++segn;
pre[segn]=u;
if(son[u])dfs2(son[u],ux);
else return;
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v==fa[u] || v==son[u])continue;
    dfs2(v,v);
}
}
 
void Update(int u,int v,long long d){
int topu=top[u],topv=top[v];
while(topu!=topv){
    if(dep[topu]<dep[topv]){swap(topu,topv);swap(u,v);}
    Modify(1,id[topu],id[u],d);
    u=fa[topu];
    topu=top[u];
}
if(dep[u]>dep[v])swap(u,v);
Modify(1,id[u],id[v],d);
}
 
long long Ask(int u,int v){
int topu=top[u],topv=top[v];
long long Sum=0;
while(topu!=topv){
    if(dep[topu]<dep[topv]){swap(topu,topv);swap(u,v);}
    Sum+=Query(1,id[topu],id[u]);
    u=fa[topu];
    topu=top[u];
}
if(dep[u]>dep[v])swap(u,v);
return Sum+Query(1,id[u],id[v]);
}
 
int main(){
freopen("4127.in","r",stdin);
freopen("4127.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
for(int i=1;i<n;i++){
    int u,v;
    scanf("%d %d",&u,&v);
    AddEdge(u,v);
    AddEdge(v,u);
}
dfs1(1,0);
dfs2(1,1);
Build(1,1,n);
while(m--){
    int opt,u,v;
    long long d;
    scanf("%d %d %d",&opt,&u,&v);
    if(opt==1){scanf("%lld",&d);Update(u,v,d);}
    if(opt==2)printf("%lld\n",Ask(u,v));
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
6
19
2016
0

[BZOJ2716] [Violet 3]天使玩偶

这个题和BZOJ2648基本是一样的

理论上直接交就能过

但是在学校的OJ上被卡到95分了很悲伤

算了就放这个BZOJ可以过但是被卡常的版本

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
 
const register int N=500005,INF=2100000000;
 
static int n,m,Sort_Tag,root,ans=INF;
 
struct KDTree{
int l,r,d[2],mn[2],mx[2];
KDTree(){}
KDTree(register int x,register int y){mn[0]=mx[0]=d[0]=x;mn[1]=mx[1]=d[1]=y;l=r=0;}
inline friend bool operator<(register KDTree A,register KDTree B){return A.d[Sort_Tag]<B.d[Sort_Tag];}
}tree[N<<2],Temp;
 
inline int Max(register int x,register int y){return x<y?y:x;}
inline int Min(register int x,register int y){return x<y?x:y;}
inline int Abs(register int x){return x>0?x:-x;}
inline int Dist(register KDTree A,register KDTree B){return Abs(A.d[0]-B.d[0])+Abs(A.d[1]-B.d[1]);}
 
inline void Pushup(register int rt){
if(tree[rt].l){
    tree[rt].mn[0]=Min(tree[rt].mn[0],tree[tree[rt].l].mn[0]);
    tree[rt].mn[1]=Min(tree[rt].mn[1],tree[tree[rt].l].mn[1]);
    tree[rt].mx[0]=Max(tree[rt].mx[0],tree[tree[rt].l].mx[0]);
    tree[rt].mx[1]=Max(tree[rt].mx[1],tree[tree[rt].l].mx[1]);
}
if(tree[rt].r){
    tree[rt].mn[0]=Min(tree[rt].mn[0],tree[tree[rt].r].mn[0]);
    tree[rt].mn[1]=Min(tree[rt].mn[1],tree[tree[rt].r].mn[1]);
    tree[rt].mx[0]=Max(tree[rt].mx[0],tree[tree[rt].r].mx[0]);
    tree[rt].mx[1]=Max(tree[rt].mx[1],tree[tree[rt].r].mx[1]);
}
}
 
inline int Build(register int l,register int r,register int D){
Sort_Tag=D;
register int mid=l+r>>1;
nth_element(tree+l,tree+mid,tree+r+1);
tree[mid].mn[0]=tree[mid].mx[0]=tree[mid].d[0];
tree[mid].mn[1]=tree[mid].mx[1]=tree[mid].d[1];
if(l<mid)tree[mid].l=Build(l,mid-1,!D);
if(r>mid)tree[mid].r=Build(mid+1,r,!D);
Pushup(mid);
return mid;
}
 
inline void _Insert(register int rt,register int D){
if(Temp.d[D]>=tree[rt].d[D]){
    if(tree[rt].r)_Insert(tree[rt].r,!D);
    else {tree[rt].r=++n;tree[n]=Temp;}
}
else {
    if(tree[rt].l)_Insert(tree[rt].l,!D);
    else {tree[rt].l=++n;tree[n]=Temp;}
}
Pushup(rt);
}
 
inline void Insert(register int x,register int y){
Temp=KDTree(x,y);
_Insert(root,0);
}
 
inline int MxDist(register int rt,register int x,register int y){
return Max(tree[rt].mn[0]-x,0)+Max(tree[rt].mn[1]-y,0)+Max(x-tree[rt].mx[0],0)+Max(y-tree[rt].mx[1],0);
}
 
inline void _Query(register int rt){
register int Dl=INF,Dr=INF,Dm=Dist(tree[rt],Temp);
ans=Min(ans,Dm);
if(tree[rt].l)Dl=MxDist(tree[rt].l,Temp.d[0],Temp.d[1]);
if(tree[rt].r)Dr=MxDist(tree[rt].r,Temp.d[0],Temp.d[1]);
if(Dl<Dr){
    if(Dl<ans)_Query(tree[rt].l);
    if(Dr<ans)_Query(tree[rt].r);
}
else {
    if(Dr<ans)_Query(tree[rt].r);
    if(Dl<ans)_Query(tree[rt].l);
}
}
 
inline int Query(register int x,register int y){
Temp=KDTree(x,y);ans=INF;
_Query(root);
return ans;
}
 
inline void Read(register int &x){
register char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=x*10+ch-'0';
}
 
int main(){
freopen("2716.in","r",stdin);
freopen("2716.out","w",stdout);
Read(n);Read(m);
for(register int i=1;i<=n;i++)Read(tree[i].d[0]),Read(tree[i].d[1]);
root=Build(1,n,0);
for(register int i=1;i<=m;i++){
    register int opt,x,y;
    Read(opt);Read(x);Read(y);
    if(opt==1)Insert(x,y);
    if(opt==2)printf("%d\n",Query(x,y));
}
return 0;
}

lzz(C_SUNSHINE)的卡常版本,比我快的不知道到哪里去了(还是不放比较好……)(就是查询时做了一些神奇的优化)

Category: BZOJ | Tags: OI bzoj
6
19
2016
0

[BZOJ3053] The Closest M Points

血崩多次……

原来KD树在二维以上的查询方式和二维不一样,我照葫芦画瓢一直是错的,改了才过

具体的,每次只查询当前划分的维度的距离才是正确的,每次递归到下一个维度时需要更改查询的维度。

感觉说的很不清晰,看代码吧

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<stack>
#include<algorithm>
using namespace std;
 
const long long N=500005,INF=210000000000000ll;
 
long long n,k,m,t,Sort_Tag,root;
priority_queue<pair<long long,long long> > PQ;
stack<long long> St;
 
struct KDTree{
long long d[5],mx[5],mn[5],l,r,id;
friend bool operator<(KDTree A,KDTree B){return A.d[Sort_Tag]<B.d[Sort_Tag];}
}tree[N],Temp;
 
void Pushup(long long rt){
if(tree[rt].l){
    for(long long i=0;i<k;i++){
        tree[rt].mx[i]=max(tree[rt].mx[i],tree[tree[rt].l].mx[i]);
        tree[rt].mn[i]=min(tree[rt].mn[i],tree[tree[rt].l].mn[i]);
    }
}
if(tree[rt].r){
    for(long long i=0;i<k;i++){
        tree[rt].mx[i]=max(tree[rt].mx[i],tree[tree[rt].r].mx[i]);
        tree[rt].mn[i]=min(tree[rt].mn[i],tree[tree[rt].r].mn[i]);
    }
}
}
 
long long Build(long long l,long long r,long long D){
Sort_Tag=D;
long long mid=l+r>>1;
nth_element(tree+l,tree+mid,tree+r+1);
for(long long i=0;i<k;i++)tree[mid].mn[i]=tree[mid].mx[i]=tree[mid].d[i];
tree[mid].l=tree[mid].r=0;
if(l<mid)tree[mid].l=Build(l,mid-1,D+1==k?0:D+1);
if(r>mid)tree[mid].r=Build(mid+1,r,D+1==k?0:D+1);
Pushup(mid);
return mid;
}
 
long long Sqr(long long x){return x*x;}
long long Dist(KDTree A,KDTree B){long long ans=0;for(long long i=0;i<k;i++)ans+=Sqr(A.d[i]-B.d[i]);return ans;}
long long MnDist(KDTree A,KDTree B){long long ans=0;for(long long i=0;i<k;i++)ans+=min(Sqr(A.d[i]-B.mn[i]),Sqr(A.d[i]-B.mx[i]));return ans;}
 
void Solve(long long rt,long long D){
long long L=tree[rt].l,R=tree[rt].r;
if(Temp.d[D]>=tree[rt].d[D])swap(L,R);
if(L)Solve(L,D+1==k?0:D+1);
long long Dis=Dist(Temp,tree[rt]);
if(Dis<PQ.top().first)PQ.pop(),PQ.push(make_pair(Dis,rt));
if(Sqr(tree[rt].d[D]-Temp.d[D])<PQ.top().first && R)Solve(R,D+1==k?0:D+1);
}
 
void Init_Solve_Out(){
while(!PQ.empty())PQ.pop();
while(!St.empty())St.pop();
for(long long i=1;i<=n;i++){
    for(long long j=0;j<k;j++)scanf("%lld",&tree[i].d[j]);
    tree[i].id=i;
}
root=Build(1ll,n,0ll);
scanf("%lld",&t);
while(t--){
    for(long long i=0;i<k;i++)scanf("%lld",&Temp.d[i]);
    scanf("%lld",&m);
    for(long long i=1;i<=m;i++)PQ.push(make_pair(INF,0));
    Solve(root,0);
    printf("the closest %lld points are:\n",m);
    while(!PQ.empty())St.push(PQ.top().second),PQ.pop();
    while(!St.empty()){
        for(long long i=0;i<k-1;i++)printf("%lld ",tree[St.top()].d[i]);
        printf("%lld\n",tree[St.top()].d[k-1]);
        St.pop();
    }
}
}

int main(){
freopen("3053.in","r",stdin);
freopen("3053.out","w",stdout);
while(~scanf("%lld %lld",&n,&k))Init_Solve_Out();
return 0;
}
Category: BZOJ | Tags: OI bzoj
6
19
2016
0

[BZOJ4520] [Cqoi2016]K远点对

这个题也是KD树搞一搞反正能过

(其实KD树复杂度不对)

最远直接做,K远那么就要搞一个堆来维护前k大值

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
 
const int N=100005,K=105;
const long long INF=999999999999999ll;
 
int n,k,Sort_Tag,root;
priority_queue<long long,vector<long long>,greater<long long> > Q;
 
struct KDTree{
long long d[2],mx[2],mn[2];
int l,r;
friend bool operator<(KDTree A,KDTree B){return A.d[Sort_Tag]<B.d[Sort_Tag];}
}tree[N<<2],Temp;
 
void Pushup(int rt){
if(tree[rt].l){
    tree[rt].mn[0]=min(tree[rt].mn[0],tree[tree[rt].l].mn[0]);
    tree[rt].mn[1]=min(tree[rt].mn[1],tree[tree[rt].l].mn[1]);
    tree[rt].mx[0]=max(tree[rt].mx[0],tree[tree[rt].l].mx[0]);
    tree[rt].mx[1]=max(tree[rt].mx[1],tree[tree[rt].l].mx[1]);
}
if(tree[rt].r){
    tree[rt].mn[0]=min(tree[rt].mn[0],tree[tree[rt].r].mn[0]);
    tree[rt].mn[1]=min(tree[rt].mn[1],tree[tree[rt].r].mn[1]);
    tree[rt].mx[0]=max(tree[rt].mx[0],tree[tree[rt].r].mx[0]);
    tree[rt].mx[1]=max(tree[rt].mx[1],tree[tree[rt].r].mx[1]);
}
}
 
int Build(int l,int r,int D){
Sort_Tag=D;
int mid=l+r>>1;
nth_element(tree+l,tree+mid,tree+r+1);
tree[mid].mx[0]=tree[mid].mn[0]=tree[mid].d[0];
tree[mid].mx[1]=tree[mid].mn[1]=tree[mid].d[1];
if(l<mid)tree[mid].l=Build(l,mid-1,!D);
if(r>mid)tree[mid].r=Build(mid+1,r,!D);
Pushup(mid);
return mid;
}
 
long long Sqr(long long x){return x*x;}
long long Dist(KDTree A,KDTree B){return Sqr(A.d[0]-B.d[0])+Sqr(A.d[1]-B.d[1]);}
long long MxDist(KDTree A,KDTree B){return max(Sqr(A.mn[0]-B.d[0]),Sqr(A.mx[0]-B.d[0]))+max(Sqr(A.mn[1]-B.d[1]),Sqr(A.mx[1]-B.d[1]));}
 
void Solve(int rt){
long long Dl=-INF,Dr=-INF,Dm=Dist(tree[rt],Temp);
if(Dm>Q.top())Q.pop(),Q.push(Dm);
if(tree[rt].l)Dl=MxDist(tree[tree[rt].l],Temp);
if(tree[rt].r)Dr=MxDist(tree[tree[rt].r],Temp);
if(Dl>Dr){
    if(Dl>=Q.top())Solve(tree[rt].l);
    if(Dr>=Q.top())Solve(tree[rt].r);
}
else {
    if(Dr>=Q.top())Solve(tree[rt].r);
    if(Dl>=Q.top())Solve(tree[rt].l);
}
}
 
int main(){
freopen("4520.in","r",stdin);
freopen("4520.out","w",stdout);
scanf("%d %d",&n,&k);
for(int i=1;i<=n;i++)scanf("%lld %lld",&tree[i].d[0],&tree[i].d[1]);
root=Build(1,n,0);
for(int i=1;i<=2*k;i++)Q.push(0);
for(int i=1;i<=n;i++){
    Temp.d[0]=tree[i].d[0];
    Temp.d[1]=tree[i].d[1];
    Solve(root);
}
printf("%lld\n",Q.top());
return 0;
}
Category: BZOJ | Tags: OI bzoj
6
19
2016
0

[BZOJ2648] SJY摆棋子

KD-Tree 模版题

查询最近点在KD树上走一走就行了

注意:此题不需要特别的卡常技巧,基本上写对了就过了(不需要重构子树、加一些玄学科技)

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
 
const int N=500005,INF=2100000000;
 
int n,m,Sort_Tag,root,ans=INF;
 
struct KDTree{
int l,r,d[2],mn[2],mx[2];
KDTree(){}
KDTree(int x,int y){mn[0]=mx[0]=d[0]=x;mn[1]=mx[1]=d[1]=y;l=r=0;}
friend bool operator<(KDTree A,KDTree B){return A.d[Sort_Tag]<B.d[Sort_Tag];}
}tree[N<<2],Temp;
 
int Abs(int x){return x>0?x:-x;}
int Dist(KDTree A,KDTree B){return Abs(A.d[0]-B.d[0])+Abs(A.d[1]-B.d[1]);}
 
void Pushup(int rt){
if(tree[rt].l){
    tree[rt].mx[0]=max(tree[rt].mx[0],tree[tree[rt].l].mx[0]);
    tree[rt].mx[1]=max(tree[rt].mx[1],tree[tree[rt].l].mx[1]);
    tree[rt].mn[0]=min(tree[rt].mn[0],tree[tree[rt].l].mn[0]);
    tree[rt].mn[1]=min(tree[rt].mn[1],tree[tree[rt].l].mn[1]);
}
if(tree[rt].r){
    tree[rt].mx[0]=max(tree[rt].mx[0],tree[tree[rt].r].mx[0]);
    tree[rt].mx[1]=max(tree[rt].mx[1],tree[tree[rt].r].mx[1]);
    tree[rt].mn[0]=min(tree[rt].mn[0],tree[tree[rt].r].mn[0]);
    tree[rt].mn[1]=min(tree[rt].mn[1],tree[tree[rt].r].mn[1]);
}
}
 
int Build(int l,int r,int D){
Sort_Tag=D;
int mid=l+r>>1;
nth_element(tree+l,tree+mid,tree+r+1);
tree[mid].mn[0]=tree[mid].mx[0]=tree[mid].d[0];
tree[mid].mn[1]=tree[mid].mx[1]=tree[mid].d[1];
if(l<mid)tree[mid].l=Build(l,mid-1,!D);
if(r>mid)tree[mid].r=Build(mid+1,r,!D);
Pushup(mid);
return mid;
}
 
void _Insert(int rt,int D){
if(Temp.d[D]>=tree[rt].d[D]){
    if(tree[rt].r)_Insert(tree[rt].r,!D);
    else {tree[rt].r=++n;tree[n]=Temp;}
}
else {
    if(tree[rt].l)_Insert(tree[rt].l,!D);
    else {tree[rt].l=++n;tree[n]=Temp;}
}
Pushup(rt);
}
 
void Insert(int x,int y){
Temp=KDTree(x,y);
_Insert(root,0);
}
 
int MxDist(int rt,int x,int y){
return max(tree[rt].mn[0]-x,0)+max(x-tree[rt].mx[0],0)+max(tree[rt].mn[1]-y,0)+max(y-tree[rt].mx[1],0);
}
 
void _Query(int rt){
int Dl=INF,Dr=INF,Dm=Dist(tree[rt],Temp);
ans=min(ans,Dm);
if(tree[rt].l)Dl=MxDist(tree[rt].l,Temp.d[0],Temp.d[1]);
if(tree[rt].r)Dr=MxDist(tree[rt].r,Temp.d[0],Temp.d[1]);
if(Dl<Dr){
    if(Dl<ans)_Query(tree[rt].l);
    if(Dr<ans)_Query(tree[rt].r);
}
else {
    if(Dr<ans)_Query(tree[rt].r);
    if(Dl<ans)_Query(tree[rt].l);
}
}
 
int Query(int x,int y){
Temp=KDTree(x,y);ans=INF;
_Query(root);
return ans;
}

int main(){
freopen("2648.in","r",stdin);
freopen("2648.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d %d",&tree[i].d[0],&tree[i].d[1]);
root=Build(1,n,0);
for(int i=1;i<=m;i++){
    int opt,x,y;
    scanf("%d %d %d",&opt,&x,&y);
    if(opt==1)Insert(x,y);
    if(opt==2)printf("%d\n",Query(x,y));
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
6
19
2016
0

[BZOJ2120] 数颜色

很多人都是使用大型数据结构写的。

我是整体二分+树状数组维护,思路是Zig_Zag大神博客上的。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<set>
#include<algorithm>
using namespace std;
 
const int N=30005,M=1000005;
 
int n,m,col[N],cnt,num,BIT[N],ans[N],tmp[N];
set<int> Color[M];
 
struct Ask{
int l,r,opt,cur,id;
}ask[N],Q1[N],Q2[N];
 
int lowbit(int x){return x&(-x);}
void Add(int pos,int val){while(pos<=n){BIT[pos]+=val;pos+=lowbit(pos);}}
int Sum(int pos){int ans=0;while(pos){ans+=BIT[pos];pos-=lowbit(pos);}return ans;}
int Pre(int x,int c){set<int>::iterator I=Color[c].lower_bound(x);if(I!=Color[c].begin())return *(--I);return 0;}
int Nxt(int x,int c){set<int>::iterator I=Color[c].upper_bound(x);if(I!=Color[c].end())return *I;return 0;}
 
void Div2x(int l,int r,int nl,int nr){
if(nl>nr)return;
int mid=l+r>>1,M1=0,M2=0;
if(l==r){for(int i=nl;i<=nr;i++)if(ask[i].opt==3)ans[ask[i].id]=ask[i].cur;return;}
for(int i=nl;i<=nr;i++){
    if(ask[i].opt==1 && ask[i].r<=mid)Add(ask[i].l,1);
    if(ask[i].opt==2 && ask[i].r<=mid)Add(ask[i].l,-1);
    if(ask[i].opt==3)tmp[i]=Sum(ask[i].r)-Sum(ask[i].l-1);
}
for(int i=nl;i<=nr;i++){
    if(ask[i].opt==1 && ask[i].r<=mid)Add(ask[i].l,-1);
    if(ask[i].opt==2 && ask[i].r<=mid)Add(ask[i].l,1);
}
for(int i=nl;i<=nr;i++){
    if(ask[i].opt==3){
        if(ask[i].l<=mid)Q1[++M1]=ask[i];
        else {ask[i].cur+=tmp[i];Q2[++M2]=ask[i];}
    }
    else {
        if(ask[i].r<=mid)Q1[++M1]=ask[i];
        else Q2[++M2]=ask[i];
    }
}
for(int i=1;i<=M1;i++)ask[nl+i-1]=Q1[i];
for(int i=1;i<=M2;i++)ask[nr-M2+i]=Q2[i];
Div2x(l,mid,nl,nl+M1-1);
Div2x(mid+1,r,nl+M1,nr);
}
 
int main(){
freopen("2120.in","r",stdin);
freopen("2120.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
    scanf("%d",&col[i]);
    Color[col[i]].insert(i);
    ask[++num].opt=1;
    int p=Pre(i,col[i]);
    ask[num].l=i;
    ask[num].r=p;
}
for(int i=1;i<=m;i++){
    char s[5];
    int l,r;
    scanf("%s %d %d",s,&l,&r);
    if(s[0]=='Q'){
        ask[++num].opt=3;
        ask[num].id=++cnt;
        ask[num].l=l;
        ask[num].r=r;
    }
    else {
        int Ll=Pre(l,col[l]),Lr=Pre(l,r),Rl=Nxt(l,col[l]),Rr=Nxt(l,r);
        if(Rl){
            ask[++num].opt=2;ask[num].l=Rl;ask[num].r=l;
            ask[++num].opt=1;ask[num].l=Rl;ask[num].r=Ll;
        }
        ask[++num].opt=2;ask[num].l=l;ask[num].r=Ll;
        ask[++num].opt=1;ask[num].l=l;ask[num].r=Lr;
        if(Rr){
            ask[++num].opt=2;ask[num].l=Rr;ask[num].r=Lr;
            ask[++num].opt=1;ask[num].l=Rr;ask[num].r=l;
        }
        Color[col[l]].erase(l);
        Color[r].insert(l);
        col[l]=r;
    }
}
Div2x(0,M,1,num);
for(int i=1;i<=cnt;i++)printf("%d\n",ans[i]);
return 0;
}
Category: BZOJ | Tags: OI bzoj
6
19
2016
0

[BZOJ4034] [HAOI2015]T2

树链剖分入门题

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
 
const int N=100005;
 
int n,m,dep[N],fa[N],son[N],siz[N],en,h[N],pre[N],segn,id[N],top[N];
long long a[N];
 
struct Edge{
int b,next;
}e[N<<1];
 
void AddEdge(int sa,int sb){
e[++en].b=sb;
e[en].next=h[sa];
h[sa]=en;
}
 
struct SegTree{
int l,r;
long long sum,tag;
}tree[N<<2];
 
void Pushdown(int rt){
if(tree[rt].tag){
    tree[rt<<1].tag+=tree[rt].tag;
    tree[rt<<1|1].tag+=tree[rt].tag;
    tree[rt<<1].sum+=tree[rt].tag*(tree[rt<<1].r-tree[rt<<1].l+1ll);
    tree[rt<<1|1].sum+=tree[rt].tag*(tree[rt<<1|1].r-tree[rt<<1|1].l+1ll);
    tree[rt].tag=0;
}
}
 
void Pushup(int rt){
tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;
}
 
void Build(int rt,int l,int r){
tree[rt].l=l;tree[rt].r=r;
if(l==r){tree[rt].sum=a[pre[l]];return;}
int mid=l+r>>1;
Build(rt<<1,l,mid);Build(rt<<1|1,mid+1,r);
Pushup(rt);
}
 
void Add(int rt,int l,int r,long long val){
if(l<=tree[rt].l && tree[rt].r<=r){tree[rt].sum+=val*(tree[rt].r-tree[rt].l+1);tree[rt].tag+=val;return;}
int mid=tree[rt].l+tree[rt].r>>1;
Pushdown(rt);
if(l<=mid)Add(rt<<1,l,r,val);
if(r>mid)Add(rt<<1|1,l,r,val);
Pushup(rt);
}
 
long long Sum(int rt,int l,int r){
if(l<=tree[rt].l && tree[rt].r<=r)return tree[rt].sum;
int mid=tree[rt].l+tree[rt].r>>1;
long long ans=0;
Pushdown(rt);
if(l<=mid)ans+=Sum(rt<<1,l,r);
if(r>mid)ans+=Sum(rt<<1|1,l,r);
return ans;
}
 
void dfs1(int u,int Fa){
dep[u]=dep[Fa]+1;
fa[u]=Fa;
siz[u]=1;
son[u]=0;
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v==Fa)continue;
    dfs1(v,u);
    siz[u]+=siz[v];
    if(siz[son[u]]<siz[v])son[u]=v;
}
}
 
void dfs2(int u,int ux){
top[u]=ux;
id[u]=++segn;
pre[segn]=u;
if(!son[u])return;
dfs2(son[u],ux);
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v!=fa[u] && v!=son[u])dfs2(v,v);
}
}
 
long long Ask(int u){
int Tp=top[u];
long long ans=0;
while(Tp!=top[1]){
    ans+=Sum(1,id[Tp],id[u]);
    u=fa[Tp];
    Tp=top[u];
}
return ans+Sum(1,id[Tp],id[u]);
}
 
int main(){
freopen("4034.in","r",stdin);
freopen("4034.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
for(int i=1;i<n;i++){
    int u,v;
    scanf("%d %d",&u,&v);
    AddEdge(u,v);AddEdge(v,u);
}
dfs1(1,1);
dfs2(1,1);
Build(1,1,n);
while(m--){
    int opt,u;
    long long val;
    scanf("%d %d",&opt,&u);
    if(opt==1){scanf("%lld",&val);Add(1,id[u],id[u],val);}
    if(opt==2){scanf("%lld",&val);Add(1,id[u],id[u]+siz[u]-1,val);}
    if(opt==3)printf("%lld\n",Ask(u));
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
6
19
2016
0

[BZOJ4033] [HAOI2015]T1

这题是一个DP

每次考虑两棵子树的贡献,然后把两棵子树合并起来,中间的转移类似树上背包

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
 
const int N=2005;
 
int n,K,en,h[N],siz[N],vis[N];
long long dp[N][N],tp[N];
 
struct Edge{
int b,next;
long long v;
}e[N<<1];
 
void AddEdge(int sa,int sb,long long sc){
e[++en].b=sb;
e[en].v=sc;
e[en].next=h[sa];
h[sa]=en;
}
 
void DP(int u){
siz[u]=vis[u]=1;
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(vis[v])continue;
    DP(v);
    for(int j=0;j<=K;j++)tp[j]=dp[u][j];
    for(int j=0;j<=min(siz[u],K);j++){
        for(int k=0;k<=min(siz[v],K);k++){
            tp[j+k]=max(tp[j+k],dp[v][k]+dp[u][j]+e[i].v*(k*(K-k)+(siz[v]-k)*(n-K-(siz[v]-k))));
        }
    }
    siz[u]+=siz[v];
    for(int j=0;j<=siz[u];j++)dp[u][j]=max(dp[u][j],tp[j]);
}
}
 
int main(){
freopen("4033.in","r",stdin);
freopen("4033.out","w",stdout);
scanf("%d %d",&n,&K);
for(int i=1;i<n;i++){
    int u,v,w;
    scanf("%d %d %d",&u,&v,&w);
    AddEdge(u,v,w);AddEdge(v,u,w);
}
DP(1);
printf("%lld\n",dp[1][K]);
return 0;
}
Category: BZOJ | Tags: OI bzoj

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com