[loj6518]序列

参考ExtremeSpanningTrees，考虑优化整体二分时求$g_{i}\in \{w_{mid},w_{mid+1}\}$的最优解

首先题目有一个条件似乎没有写出来，是保证$l\le k\le r$的（但并不是特别重要，可能更方便）

可以发现只关心于$k$属于当前考虑的点集中的询问即可，因此每一次层的限制数为$o(m)$（可以通过上面的条件，将区间求并后优化为$o(n)$个）

考虑用线段树来优化建图，具体来说，分为以下几步：

1.将点以及区间离散到点个数长度的区间，来保证复杂度；

2.建两颗线段树，左边的线段树从儿子到父亲，右边的线段树从父亲到儿子（流量inf）

3.每一个点连向左边对应的叶子，右边的叶子连向对应的点，根据权值划分到$S$和$T$

4.对于初始$k$到$[l,r]$的边，对应为$k$在左边的叶子连向右边$[l,r]$对应的log个区间，反之类似

理论时间复杂度为$o(n^{3}\log^{2}n)$，可以通过

  1 #include<bits/stdc++.h>

  2 using namespace std;

  3 #define N 5005

  4 #define ll long long

  5 #define oo 0x3f3f3f3f

  6 #define vi vector<int>

  7 #define L (k<<1)

  8 #define R (L+1)

  9 struct ji{

 10     int nex,to,len;

 11 }edge[N<<5];

 12 queue<int>q;

 13 int n,m,p,l,r,k,lx[N][2],rx[N][2],w[N],v[N],a[N],ans[N];

 14 int V,E,leaf[N],head[N<<4],work[N<<4],d[N<<4],vis[N<<4],bl[N];

 15 bool cmp(int x,int y){

 16     return (bl[x]<bl[y])||(bl[x]==bl[y])&&(x<y);

 17 }

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

 19     edge[E].nex=head[x];

 20     edge[E].to=y;

 21     edge[E].len=z;

 22     head[x]=E++;

 23     if (E&1)add(y,x,0);

 24 }

 25 bool bfs(){

 26     memset(d,oo,sizeof(d));

 27     d[0]=0;

 28     q.push(0);

 29     while (!q.empty()){

 30         int k=q.front();

 31         q.pop();

 32         for(int i=head[k];i!=-1;i=edge[i].nex)

 33             if ((edge[i].len)&&(d[edge[i].to]==oo)){

 34                 d[edge[i].to]=d[k]+1;

 35                 q.push(edge[i].to);

 36             }

 37     }

 38     return d[(V<<1)+n+1]<oo;

 39 }

 40 int dfs(int k,int s){

 41     if (k>(V<<1)+n)return s;

 42     for(int &i=work[k];i!=-1;i=edge[i].nex)

 43         if ((edge[i].len)&&(d[edge[i].to]==d[k]+1)){

 44             int p=dfs(edge[i].to,min(s,edge[i].len));

 45             if (p){

 46                 edge[i].len-=p;

 47                 edge[i^1].len+=p;

 48                 return p;

 49             }

 50         }

 51     return 0;

 52 }

 53 void dinic(){

 54     while (bfs()){

 55         memcpy(work,head,sizeof(work));

 56         while (dfs(0,oo));

 57     }

 58 }

 59 void dfs(int k){

 60     if (vis[k])return;

 61     vis[k]=1;

 62     for(int i=head[k];i!=-1;i=edge[i].nex)

 63         if (edge[i].len)dfs(edge[i].to);

 64 }

 65 void build(int k,int l,int r){

 66     if (l==r){

 67         leaf[l]=k;

 68         V=max(V,k);

 69         return;

 70     }

 71     int mid=(l+r>>1);

 72     build(L,l,mid);

 73     build(R,mid+1,r);

 74 }

 75 void update(int k,int l,int r,int x,int y,int z,int p){

 76     if ((l>y)||(x>r))return;

 77     if ((x<=l)&&(r<=y)){

 78         if (p)add(k,z+V,oo);

 79         else add(z,k+V,oo);

 80         return;

 81     }

 82     int mid=(l+r>>1);

 83     update(L,l,mid,x,y,z,p);

 84     update(R,mid+1,r,x,y,z,p);

 85 }

 86 void dfs(int l,int r,int x,int y){

 87     if (x==y){

 88         for(int i=l;i<=r;i++)ans[a[i]]=v[x];

 89         return;

 90     }

 91     int mid=(x+y>>1);

 92     V=E=0;

 93     build(1,1,r-l+1);

 94     for(int i=0;i<=(V<<1)+n+1;i++)head[i]=-1;

 95     for(int i=2;i<=V;i++){

 96         add(i,i/2,oo);

 97         add(i/2+V,i+V,oo);

 98     }

 99     for(int i=l;i<=r;i++){//若i比j小则i向j连边，源点连大的，汇点连小的

100         add((V<<1)+i,leaf[i-l+1],oo);

101         add(leaf[i-l+1]+V,(V<<1)+i,oo);

102         if (w[a[i]]>=v[mid+1])add(0,(V<<1)+i,1);

103         else add((V<<1)+i,(V<<1)+n+1,1);

104     }

105     for(int i=l;i<=r;i++)

106         for(int j=0;j<2;j++){

107             int x=lx[a[i]][j],y=rx[a[i]][j];

108             int wx=lower_bound(a+l,a+r+1,x)-a-l+1,wy=upper_bound(a+l,a+r+1,y)-a-l;

109             if (wx<wy)update(1,1,r-l+1,wx,wy,leaf[i-l+1],j);

110         }

111     dinic();

112     for(int i=0;i<=(V<<1)+n+1;i++)vis[i]=0;

113     dfs(0);

114     for(int i=l;i<=r;i++){

115         if ((w[a[i]]>=v[mid+1])&&(vis[leaf[i-l+1]])||(w[a[i]]<v[mid+1])&&(vis[leaf[i-l+1]+V]))bl[a[i]]=1;

116         else bl[a[i]]=0;

117     }

118     sort(a+l,a+r+1,cmp);

119     for(int i=l;i<=r+1;i++){

120         if ((bl[a[i]])||(i>r)){

121             if (l<i)dfs(l,i-1,x,mid);

122             if (i<=r)dfs(i,r,mid+1,y);

123             return;

124         }

125     }

126 }

127 int main(){

128     scanf("%d%d",&n,&m);

129     for(int i=1;i<=n;i++)scanf("%d",&w[i]);

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

131         for(int j=0;j<2;j++)lx[i][j]=rx[i][j]=i;

132     for(int i=1;i<=m;i++){

133         scanf("%d%d%d%d",&p,&l,&r,&k);

134         lx[k][p]=min(lx[k][p],l);

135         rx[k][p]=max(rx[k][p],r);

136     }

137     memcpy(v,w,sizeof(v));

138     sort(v+1,v+n+1);

139     int nn=unique(v+1,v+n+1)-v-1;

140     for(int i=1;i<=n;i++)a[i]=i;

141     dfs(1,n,1,nn);

142     long long sum=0;

143     for(int i=1;i<=n;i++)sum+=abs(ans[i]-w[i]);

144     for(int i=1;i<=n;i++){

145         for(int j=lx[i][0];j<=rx[i][0];j++)assert(ans[j]>=ans[i]);

146         for(int j=lx[i][1];j<=rx[i][1];j++)assert(ans[j]<=ans[i]);

147     }

148     printf("%lld",sum);

149 }

巴特西

[loj6518]序列

最新文章

热门文章