UNR#3 Day1——[ 堆+ST表+复杂度分析 ][ 结论 ][ 线段树合并 ]

时间：2023-03-09 04:27:24
UNR#3 Day1——[ 堆+ST表+复杂度分析 ][ 结论 ][ 线段树合并 ]

地址：http://uoj.ac/contest/45

第一题是鸽子固定器。

　　只会10分。按 s 从小到大排序，然后 dp[ i ][ j ][ k ] 表示前 i 个元素、已经选了 j 个、最小值所在位置是 k 的最大代价。

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

int rdn()

{

  int ret=;bool fx=;char ch=getchar();

  while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return fx?ret:-ret;

}

ll Mx(ll a,ll b){return a>b?a:b;}

ll Mn(ll a,ll b){return a<b?a:b;}

const int N=,M=;

int n,m,ds,dv,f[M][N]; ll ans=-1e18;

struct Node{

  int s,v;

  bool operator< (const Node &b)const

  {return s<b.s;}

}a[N];

ll calv(int x)

{ if(dv==)return x;return (ll)x*x;}

ll cals(int x)

{ if(ds==)return x;return (ll)x*x;}

int main()

{

  n=rdn();m=rdn();ds=rdn();dv=rdn();

  for(int i=;i<=n;i++)

    a[i].s=rdn(),a[i].v=rdn();

  sort(a+,a+n+);

  for(int i=;i<=n;i++)

    {

      for(int j=Mn(i,m);j>;j--)

    for(int k=;k<i;k++)

      {

        ans=Mx(ans,calv(f[j-][k]+a[i].v)-cals(a[i].s-a[k].s));

        f[j][k]=Mx(f[j][k],f[j-][k]+a[i].v);

      }

      f[][i]=a[i].v;

      ans=Mx(ans,calv(a[i].v));

    }

  printf("%lld\n",ans);

  return ;

}

囧

　　当 ds=dv=1 的时候，不用考虑最小值是多少，只要考虑新增一个元素的代价。也就是原来的最后一个元素不是最大值、自己才是最大值。

　　那么 \( dp[i][j] \) 表示前 i 个选 j 个、一定选了第 i 个；这样就知道第 i 个是当前的最后一个。

　　转移只需 \( dp[i][j]=v[i]+s[i]+\max\limits_{1<=k<i} dp[k][j-1]-s[k] \) ；前缀最大值优化 DP 。没有实现。

　　应该考虑不仅用 DP 来做。

　　注意到一个暴力做法：确定 r ，枚举 l ；那么中间选择的一定是 v 最大的一些元素。那么维护对于 v 的小根堆，看看 l 能否取代堆顶即可。

　　1.一旦 r 被弹出堆，就直接枚举下一个 r ； 2.用 ST 表来二分寻找下一个 l （下一个 v 大于堆顶的元素）。

　　根据题解的证明，这样复杂度是 O(nmlogn) ，可过。虽然还可以做到 O(nm) ，但没有实现。

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

#define ll long long

using namespace std;

int rdn()

{

  int ret=;bool fx=;char ch=getchar();

  while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return fx?ret:-ret;

}

ll Mx(ll a,ll b){return a>b?a:b;}

ll Mn(ll a,ll b){return a<b?a:b;}

const int N=2e5+,K=;

int n,m,ds,dv,lg[N],bin[K],mx[N][K]; ll ans;

struct Node{

  int s,v;

  bool operator< (const Node &b)const

  {return s<b.s;}

}a[N];

priority_queue<int,vector<int>,greater<int> > q;

ll cal(int v,int s){return (dv==?v:(ll)v*v)-(ds==?s:(ll)s*s);}

int main()

{

  n=rdn();m=rdn();ds=rdn();dv=rdn();

  for(int i=;i<=n;i++)

    a[i].s=rdn(), a[i].v=rdn();

  for(int i=;i<=n;i++)lg[i]=lg[i>>]+;

  bin[]=;for(int i=;i<=lg[n]+;i++)bin[i]=bin[i-]<<;//+1

  sort(a+,a+n+);

  for(int i=;i<=n;i++)

    {

      mx[i][]=a[i].v;

      for(int t=;i>=bin[t];t++)

    mx[i][t]=Mx(mx[i][t-],mx[i-bin[t-]][t-]);

    }

  for(int i=,j;i<=n;i++)

    {

      while(q.size())q.pop(); int sm=;

      for(j=i;j&&j>i-m;j--)

    {

      q.push(a[j].v);sm+=a[j].v;

      ans=Mx(ans,cal(sm,a[i].s-a[j].s));

    }

      while()

    {

      int d=q.top(); if(d==a[i].v)break;

      for(int t=lg[j];t>=;t--)

        if(bin[t]<=j&&mx[j][t]<=d)j-=bin[t];//bin[t]<=j

      if(!j)break;

      q.pop(); q.push(a[j].v); sm+=a[j].v-d;

      ans=Mx(ans,cal(sm,a[i].s-a[j].s));

      j--;/////

    }

    }

  printf("%lld\n",ans);

  return ;

}

第二题是 To Do Tree 。

　　每次把新解锁的点放进堆里，每次操作取出向下的 dep 前 m 大的元素即可。不太会证明……

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

int rdn()

{

  int ret=;bool fx=;char ch=getchar();

  while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return fx?ret:-ret;

}

int Mx(int a,int b){return a>b?a:b;}

int Mn(int a,int b){return a<b?a:b;}

const int N=1e5+;

int n,m,hd[N],xnt,to[N<<],nxt[N<<];

int dep[N],p[N],tot,ct[N],cnt;

struct cmp{

  bool operator() (const int &a,const int &b)const

  {return dep[a]<dep[b];}

};

priority_queue<int,vector<int>,cmp> q;

void add(int x,int y)

{

  to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;

}

void dfs(int cr)

{

  for(int i=hd[cr],v;i;i=nxt[i])

    {

      dfs(v=to[i]); dep[cr]=Mx(dep[cr],dep[v]+);

    }

}

int main()

{

  n=rdn();m=rdn();

  for(int i=,d;i<=n;i++)

    { d=rdn();add(d,i);}

  dfs(); q.push();

  while(q.size())

    {

      cnt++; int lst=tot;

      while(q.size())

    {

      p[++tot]=q.top(); q.pop();

      if(tot-lst==m)break;

    }

      ct[cnt]=tot-lst;

      for(int i=lst+;i<=tot;i++)

    for(int j=hd[p[i]];j;j=nxt[j])

      q.push(to[j]);

    }

  printf("%d\n",cnt);

  for(int i=,nw=;i<=cnt;i++)

    {

      printf("%d ",ct[i]);

      for(int j=;j<=ct[i];j++,nw++)

    printf("%d ",p[nw]); puts("");

    }

  return ;

}

第三题是配对树。

　　不知道怎么不枚举序列上的区间。

　　考虑 m2 枚举区间。把区间里的元素“加入”表示树上该点到根的链上点的状态都取反。树点的状态为 0/1 表示其子树里有 偶数/奇数 个区间里的点；如果状态是 1 的话，该点连向父亲的边需要加入答案。

　　用 LCT 维护这个过程。区间 (L-2,R) 可以继承 (L,R) 的状态。应该是 O( m2logn ) 的，但是在链的数据上实测很慢。不 makeroot 而每次 access 的 LCT 复杂度？总之得了20分。

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

#define ls c[x][0]

#define rs c[x][1]

using namespace std;

int rdn()

{

  int ret=;bool fx=;char ch=getchar();

  while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return fx?ret:-ret;

}

const int N=1e5+,mod=;

int upt(int x){while(x>=mod)x-=mod;while(x<)x+=mod;return x;}

int n,m,a[N],hd[N],xnt,to[N<<],nxt[N<<],w[N<<],ans,prn;

int fa[N],c[N][],vl[N],sm[N],s2[N]; bool tg[N],b[N];

bool rv[N];

int sta[N],top;

void add(int x,int y,int z)

{ to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;w[xnt]=z;}

void dfs(int cr,int f)

{

  fa[cr]=f;

  for(int i=hd[cr],v;i;i=nxt[i])

    if((v=to[i])!=f)

      {

    vl[v]=sm[v]=w[i]; dfs(v,cr);

      }

}

bool isrt(int x){return c[fa[x]][]!=x&&c[fa[x]][]!=x;}

void pshd(int x)

{

  if(rv[x])

    {

      rv[x]=; if(ls)rv[ls]^=; if(rs)rv[rs]^=; swap(ls,rs);

    }

  if(!tg[x])return; tg[x]=;

  if(ls) s2[ls]=upt(sm[ls]-s2[ls]), tg[ls]^=, b[ls]^=;

  if(rs) s2[rs]=upt(sm[rs]-s2[rs]), tg[rs]^=, b[rs]^=;

}

void pshp(int x)

{

  sm[x]=upt(sm[ls]+sm[rs]); sm[x]=upt(sm[x]+vl[x]);

  s2[x]=upt(s2[ls]+s2[rs]); if(b[x])s2[x]=upt(s2[x]+vl[x]);

}

void rotate(int x)

{

  int y=fa[x],z=fa[y]; bool d=(x==c[y][]);

  if(!isrt(y))c[z][y==c[z][]]=x;

  fa[x]=z; fa[y]=x; fa[c[x][!d]]=y;

  c[y][d]=c[x][!d]; c[x][!d]=y;

  pshp(y); pshp(x);

}

void splay(int x)

{

  sta[top=]=x;

  for(int k=x;fa[k];k=fa[k])sta[++top]=fa[k];

  for(int i=top;i;i--)pshd(sta[i]);

  for(int y,z;!isrt(x);rotate(x))

    {

      y=fa[x];z=fa[y];

      if(!isrt(y))

    ((x==c[y][])^(y==c[z][]))?rotate(x):rotate(y);

    }

}

void access(int x)

{

  for(int t=;x;t=x,x=fa[x])

    {

      splay(x);//tg[x]=0

      c[x][]=t; pshp(x);

    }

}

void mkrt(int x)

{

  access(x); splay(x); rv[x]^=; swap(ls,rs);

}

void cz(int x)

{

  if(rand()&)

    {

      mkrt(); access(x); splay(x);

      int y=s2[x];

      s2[x]=upt(sm[x]-s2[x]); tg[x]^=; b[x]^=;

      ans=upt(ans+s2[x]-y);

    }

  else

    {

      mkrt(x); access(); splay();

      int y=s2[];

      s2[]=upt(sm[]-s2[]); tg[]^=; b[]^=;

      ans=upt(ans+s2[]-y);

    }

}

int main()

{

  srand();

  n=rdn();m=rdn();

  for(int i=,u,v,w;i<n;i++)

    {

      u=rdn();v=rdn();w=rdn()%mod;

      add(u,v,w); add(v,u,w);

    }

  for(int i=;i<=m;i++)a[i]=rdn();

  dfs(,);

  for(int i=;i<=m;i++)

    {

      for(int j=i;j>;j-=)

    {

      cz(a[j]); cz(a[j-]); prn=upt(prn+ans);

    }

      ans=; for(int j=;j<=n;j++)s2[j]=, tg[j]=b[j]=;

    }

  printf("%d\n",prn);

  return ;

}

囧

　　不枚举序列上的区间的方法就是直接考虑一条树边被算了几次。

　　把一个点的子树里的节点对应的序列上的位置都赋值为1。有多少个 “长度为偶数且包含了奇数个1” 的区间，该点连向父亲的边就被算了多少次。

　　因为是把子树里的点的位置都赋值为1，所以考虑线段树合并。

　　又注意到长度为偶数的区间 ( L, R ) ，R 和 L-1 的奇偶性相同；所以分开考虑序列的奇数位置和偶数位置，维护“前缀和为奇数/偶数”的个数即可。区间合并的时候看左区间若有奇数个1，就需要把右区间的奇/偶翻转再加到自己身上。

　　注意动态开点的话，pshp 的时候小心没有左/右孩子的情况。

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#define ll long long

#define ls Ls[cr]

#define rs Rs[cr]

using namespace std;

int rdn()

{

  int ret=;bool fx=;char ch=getchar();

  while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return fx?ret:-ret;

}

const int N=1e5+,M=N*,mod=;

int upt(int x){while(x>=mod)x-=mod;while(x<)x+=mod;return x;}

void Add(int &x,int y){x=upt(x+y);}

int n,m,hd[N],xnt,to[N<<],nxt[N<<],w[N<<],ans;

int rt[N],tot,Ls[M],Rs[M],sm[M],ct[M][];

vector<int> ps[N];

void add(int x,int y,int z)

{ to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;w[xnt]=z;}

int cal(bool fx,int l,int r)

{

  if(!fx)return (r>>)-((l-)>>);//if l==0 then +1

  return ((r+)>>)-(l>>);

}

void pshp(int cr,int l,int mid,int r)

{

  sm[cr]=sm[ls]+sm[rs];

  for(int i=;i<=;i++)ct[cr][i]=ct[ls][i];

  if(sm[ls]&)

    for(int i=;i<=;i++)

      Add(ct[cr][i],cal(i,mid+,r)-ct[rs][i]);//-ct...

  else

    for(int i=;i<=;i++)

      Add(ct[cr][i],ct[rs][i]);

}

void mrg(int l,int r,int &cr,int pr)

{

  if(!cr){cr=pr;return;} if(!pr)return;

  int mid=l+r>>;

  mrg(l,mid,ls,Ls[pr]); mrg(mid+,r,rs,Rs[pr]);

  pshp(cr,l,mid,r);

}

void mdfy(int l,int r,int &cr,int p)

{

  if(!cr) cr=++tot;

  if(l==r)

    {

      if(l&)ct[cr][]++; else ct[cr][]++;

      sm[cr]=; return;

    }

  int mid=l+r>>;

  if(p<=mid)mdfy(l,mid,ls,p); else mdfy(mid+,r,rs,p);

  pshp(cr,l,mid,r);

}

void dfs(int cr,int fa,int tw)

{

  for(int i=hd[cr],v;i;i=nxt[i])

    if((v=to[i])!=fa)

      {

    dfs(v,cr,w[i]); mrg(,m,rt[cr],rt[v]);

      }

  for(int i=,lm=ps[cr].size();i<lm;i++)

    mdfy(,m,rt[cr],ps[cr][i]);

  int r=rt[cr];

  ans=(ans+(ll)ct[r][]*(cal(,,m)-ct[r][])%mod*tw)%mod;

  ans=(ans+(ll)ct[r][]*(cal(,,m)-ct[r][])%mod*tw)%mod;

}

int main()

{

  n=rdn();m=rdn();

  for(int i=,u,v,z;i<n;i++)

    {

      u=rdn();v=rdn();z=rdn();

      add(u,v,z);add(v,u,z);

    }

  for(int i=,d;i<=m;i++)

    { d=rdn();ps[d].push_back(i);}

  dfs(,,); printf("%d\n",ans);

  return ;

}