kczno1的博客官方,网上题解似乎都是$O(nlogn)$的
$dp[i]$表示$1..i$的$min$
则$dp[i]=min(dp[j-1]+max(h[j..i]))$ 且$w(j)+..w(i)<=L$
从左到右枚举$i$，
则所有$j$被所有$h[k]=max(h[k..i])$的$k$分成一段一段
每段由于$dp[j]$的单调递增肯定取最左边的那个$j$
$k$可以用单调栈维护
由于$w(j)+..w(i)$的限制，可以的$j$的左边界是单调左移的
我想了一个$O(n)$的方法，而且是能解决两端插入的 (求问有没有别的方法)
就是左右各开一个栈维护最值，
左边删除插入就用左边的
右边删除插入就用右边的
如果左或右的栈删没了，就重构，把队列分成两半，左边分一半，右边分一半
每次重构的时间复杂度和下次删完所需的时间是一样的，所以复杂度是线性的。
卡常后拿了bzoj rank1
网上题解似乎都是可并堆。
这题可以给每个点自己+1,上面第一个距离>=l的祖先-1，然后统计子树和，即为答案。
求那个祖先可以dfs一遍，把点存在栈里，然后二分。
$O(nlogn)$
能拿bzoj rank1。
#include<cstdio>
using namespace std;
typedef long long ll;
#define pb push_back
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define per(i,r,l) for(int i=r;i>=l;--i)
template <typename T> inline void chmin(T &x,const T &y)
{
if(x>y)x=y;
}
template <typename T> inline void chmax(T &x,const T &y)
{
if(x<y)x=y;
}
const int ch_top=1e7;
char ch[ch_top],*now_r=ch-1,*now_w=ch-1;
#define gc (*++now_r)
#define c *now_r
void read(int &x)
{
while(gc<'0');
x=c-'0';
while(gc>='0')x=x*10+c-'0';
}
void read(ll &x)
{
while(gc<'0');
x=c-'0';
while(gc>='0')x=x*10+c-'0';
}
#undef gc
#undef c
void write(int x)
{
static char st[20];
int top=0;
do{st[++top]='0'+x%10;}while(x/=10);
do{*++now_w=st[top];}while(--top);
*++now_w='\n';
}
const int N=2e5+5;
int n,t[N],nex[N];
ll l,a[N];
ll st[N];int stx[N],top;
int s[N];
void find(const ll &ns,int r)//将第一个<=ns的祖先-1
{
int l=1;
if(st[r]<=ns){--s[stx[r]];return ;}
#define mid (l+r>>1)
while(l+1!=r)
if(st[mid]<=ns)l=mid;
else r=mid;
--s[stx[l]];
}
void dfs(int x,const ll &ns,int dep)
{
st[dep]=ns;stx[dep]=x;
if(ns>=l)
{
find(ns-l,dep-1);
}
s[x]=1;
for(int y=t[x];y;y=nex[y])
{
dfs(y,ns+a[y],dep+1);
s[x]+=s[y];
}
}
int main()
{
freopen("1.in","r",stdin);//freopen("1.out","w",stdout);
ch[fread(ch,1,ch_top,stdin)]=0;
read(n);read(l);l+=1;
rep(i,2,n)
{
int x;
read(x);read(a[i]);
nex[i]=t[x];t[x]=i;
}
dfs(1,0,1);
rep(i,1,n)write(s[i]);
fwrite(ch,1,now_w-ch+1,stdout);
}这题很多人都用DP+可并堆
也有很多人暴力上堆 复杂度是$klogk$乘上128以内的质因数个数，约30(不过实际效果挺好的)
然而直接上堆，可以做到$2*k$次$push$,$k$次$pop$ 。
首先枚举所有可能的最大质因子及质因子分解的项数
这样题目的限制就没了，每次拓展时就可以除掉一个质因数再乘上一个质因数(只要别把最大质因子除没了)
考虑如何可以使得所有数会被拓展到且只会被拓展到一次
一个想法就是每次拓展时除掉最小质因子再乘上其前驱(比它小的最大质数)
但对于一个有多个质因子的数这样还是不能拓展到
所以再加一个方向:除掉最大质因子再乘上最小质因子
这样就ok了。
$O(klogk)$
拿到了bzoj rank3。 (下面这个直接用priority_queue的就能拿rank5，后来我手写了二叉堆。 我还写了配对堆，但不知道为什么慢了一倍多)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define per(i,r,l) for(int i=r;i>=l;--i)
const int N=128;
int pr[N],cnt;
struct point
{
ll a;
int b,c,d;
point( ll a , int b , int c , int d ) : a( a ) , b( b ) , c( c ) , d( d ) {}
};
bool operator <(const point &p1,const point &p2)
{
return p1.a<p2.a;
}
priority_queue<point> h;
bool is_p(int x)
{
for(int i=2;i*i<=x;++i)
if(x%i!=0) return 0;
return 1;
}
int main()
{
//freopen("1.in","r",stdin);//freopen("1.out","w",stdout);
ll n;int k;
cin>>n>>k;
rep(i,2,N)
if(is_p(i))
{
pr[++cnt]=i;
ll a=1;
for(int j=1;a<=n/i;++j)
{
a*=i;
h.push( point(a,i,0,0) );
if(cnt>1&&j>1)
h.push( point(a/i*pr[cnt-1],i,j-1,cnt-1) );
}
}
while(--k)
{
point now=h.top();
h.pop();
if(now.d>1)
h.push( point( now.a/pr[now.d]*pr[now.d-1],now.b,now.c,now.d-1 ) );
if(now.c>1)
h.push( point( now.a/now.b*pr[now.d],now.b,now.c-1,now.d ) );
}
cout<<h.top().a;
}标算复杂度似乎是$O(3^{n}*n^2)$的，但可以$O(2^{n}*n^3)$
首先枚举哪些点是叶子。(设枚举的点集为 $s_1$,剩下的点集为 $s_2$)
如何保证一个点 $i$ 是叶子？
只要让 $i$ 往 $s_2$ 连一条边就可以了。
所以方案数 $f[s_1]=$ $s_2$ 的生成树个数 $ \times \prod_{i,i \in s_1}$ $i$ 连向 $s_2$ 的边数。前一项可以用矩阵树求
但这样其实只能保证 ${\textbf s_1}$ 的点是叶子，却不能保证 ${\textbf s_2}$ 的点不是叶子。
现在要求只有 ${\textbf s}$ 的点是叶子的方案数 $ans[s]$，就再容斥一下:
$ ans[s]=\sum_{s',s' \supseteq s } f[s'] * (-1)^{|s'|-|s|} $
这个东西如果暴力的话因为每个点有三种状态所以复杂度$O(3^{n})$
但他其实类似高维前缀和，于是可以$O(2^{n}*n)$
答案就是$\sum_{s,|s|=k} ans[s]$
总复杂度是$\sum_{i=0}^{s} cnt[s-i]^{3}$ , 其中$s=2^{n}-1$,$cnt[s]$ 表示二进制数 $s$ 中 $1$ 的个数
当$n=10$时，这个值为$166400$
但我也不会算，就当它是$O(2^{n}*n^3)$吧
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
typedef long long ll;
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define gc (c=getchar())
int read()
{
char c;
while(gc<'-');
if(c=='-')
{
int x=gc-'0';
while(gc>='0')x=x*10+c-'0';
return -x;
}
int x=c-'0';
while(gc>='0')x=x*10+c-'0';
return x;
}
template <typename T> void chmin(T &x,const T &y)
{
if(x>y)x=y;
}
template <typename T> void chmax(T &x,const T &y)
{
if(x<y)x=y;
}
struct vec
{
int *a,n;
void pb(int x)
{
if(n==(n&-n))
{
int *_a=new int [n*2];
memcpy(_a,a,n*sizeof(int));
a=_a;
}
a[n++]=x;
}
};
const int N=10,U=1<<N;
int lk[N][N];
ll f[U];
int q[N];
ll qa[N][N],*a[N];
ll gauss(int m)
{
ll ans=1;
for(int i=0;i<m;++i)
{
for(int j=i+1;j<m;++j)
{
while(a[j][i])
{
ll bi=a[i][i]/a[j][i];
for(int k=i;k<m;++k)
a[i][k]-=a[j][k]*bi;
swap(a[i],a[j]);
ans=-ans;
}
}
ans*=a[i][i];
}
return ans;
}
int main()
{
freopen("1.in","r",stdin);//freopen("1.out","w",stdout);
for(int i=0;i<N;++i)a[i]=qa[i];
int n=read(),m=read(),k=read();
while(m--)
{
int x=read()-1,y=read()-1;
++lk[x][y];++lk[y][x];
}
int u=(1<<n)-1;
for(int s=1;s<u;++s)
{
ll ans=1;
m=0;
for(int i=0;i<n;++i)
if(!(s&(1<<i))) q[m++]=i;
for(int i=0;i<n;++i)
if(s&(1<<i))
{
int cnt=0;
for(int j=0;j<m;++j) cnt+=lk[i][q[j]];
ans*=cnt;
}
for(int i=0;i<m;++i)
for(int j=0;j<m;++j)
a[i][j]=0;
for(int i=0;i<m;++i)
for(int j=0;j<i;++j)
{
int w=lk[q[i]][q[j]];
a[i][i]+=w;
a[j][j]+=w;
a[i][j]=a[j][i]=-w;
}
ans*=gauss(m-1);
if((n-m-k)%2==1) f[s]=-ans;
else f[s]=ans;
}
for(int i=0;i<n;++i)
for(int s=0;s<u;++s)
if( (s&(1<<i))==0 ) f[s]+=f[s+(1<<i)];
ll ans=0;
for(int s=0;s<u;++s)
{
int cnt=0;
for(int i=0;i<n;++i)
if(s&(1<<i))++cnt;
if(cnt==k)ans+=f[s];
}
cout<<ans;
}先在线段树上二分得到 满足子树点权和>=总点权/2的 dfs序最大的点x
之后再考虑计算带权距离和，即 $ans(x)= \sum_{i} dis(i,x) * v[i]$
因为$dis(i,x)=deep[i]+deep[x]-2*deep[lca]$
所以$ans(x)=(\sum_{i} deep[i] * v[i]) + (deep[x]*\sum_{i} v[i]) -2*(\sum_{i} v[i]*deep[lca]) $
前两项直接维护
最后一个式子怎么算呢
就是每次 $v[i]$+=$x$ 就把$i$到根的路径上的点的$add$全部+=$x$
查询$ans(x)$时 就查询x到根的$\sum_{i} add[i]*(deep[i]-deep[fa[i]])$
线段树预处理区间$\sum_{i}(deep[i]-deep[fa[i]])$后可以维护
时间$O(nlog^2)$ 跑的还是挺快的
# pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define pb push_back
const int ch_top=1e7;
char ch[ch_top],*now_r=ch-1,*now_w=ch-1;
int read()
{
while(*++now_r<'-');
if(*now_r=='-')
{
int x=*++now_r-'0';
while(*++now_r>='0')x=x*10+*now_r-'0';
return -x;
}
int x=*now_r-'0';
while(*++now_r>='0')x=x*10+*now_r-'0';
return x;
}
void write(ll x)
{
static char st[20];static int top;
if(!x)*++now_w='0';
else
{
do{st[++top]='0'+x%10;}while(x/=10);
do{*++now_w=st[top];}while(--top);
}
*++now_w='\n';
}
const int N=1e5+5,T=N*4;
struct edge
{
int to,w;
};
int n,m;
vector<edge>lk[N];
int fa[N],deep[N],sz[N],son[N],top[N],dfn[N],tot;
int q[N];
void dfs(int x,int fr,int dep)
{
fa[x]=fr;deep[x]=dep;sz[x]=1;
vector<edge>::iterator i=lk[x].begin();
while(i!=lk[x].end())
{
int y=i->to;
if(y==fr){++i;continue;}
dfs(y,x,dep+i->w);
sz[x]+=sz[y];
if(sz[y]>sz[son[x]])son[x]=y;
++i;
}
}
void dfs2(int x,int ntop)
{
q[dfn[x]=++tot]=x;top[x]=ntop;
if(!son[x])return ;
dfs2(son[x],ntop);
for(vector<edge>::iterator i=lk[x].begin();i!=lk[x].end();++i)
{
int y=i->to;
if(y==son[x]||y==fa[x])continue;
dfs2(y,y);
}
}
int x,w;
ll xs,s;
#define mid (l+r>>1)
#define cl (k*2)
#define cr (cl+1)
namespace seg
{
int ad[T],mx[T];ll s[T],xs[T];
int ql,qr;
inline void _add(int k,int x)
{
ad[k]+=x;mx[k]+=x;
xs[k]+=s[k]*x;
}
inline void down(int k)
{
if(ad[k]){_add(cl,ad[k]);_add(cr,ad[k]);ad[k]=0;}
}
inline void up(int k)
{
mx[k]=max(mx[cl],mx[cr]);
xs[k]=xs[cl]+xs[cr];
}
void add(int k,int l,int r)
{
if(ql<=l&&qr>=r){_add(k,w);return ;}
down(k);
if(ql<=mid)add(cl,l,mid);
if(qr>mid)add(cr,mid+1,r);
up(k);
}
void add(int l,int r)
{
ql=l;qr=r;
add(1,1,n);
}
void init(int k,int l,int r)
{
if(l==r)
{
s[k]=deep[q[l]]-deep[fa[q[l]]];
return ;
}
init(cl,l,mid);init(cr,mid+1,r);
s[k]=s[cl]+s[cr];
}
int qiu(const ll &x)
{
int k=1,l=1,r=n;
while(l!=r)
{
down(k);
if(mx[cr]>=x) {k=cr;l=mid+1;}
else {k=cl;r=mid;}
}
return l;
}
ll ans;
void qiu(int k,int l,int r)
{
if(ql<=l&&qr>=r){ans+=xs[k];return ;}
down(k);
if(ql<=mid)qiu(cl,l,mid);
if(qr>mid)qiu(cr,mid+1,r);
}
ll qiu(int l,int r)
{
ql=l;qr=r;ans=0;
qiu(1,1,n);
return ans;
}
};
void add_to_rt(int x)
{
while(x)
{
int f=top[x];
seg::add(dfn[f],dfn[x]);
x=fa[f];
}
}
ll qiu_s(int x)
{
ll ans=0;
while(x)
{
int f=top[x];
ans+=seg::qiu(dfn[f],dfn[x]);
x=fa[f];
}
return ans;
}
int main()
{
freopen("1.in","r",stdin);freopen("1.out","w",stdout);
fread(ch,1,ch_top,stdin);
n=read();m=read();
rep(i,1,n-1)
{
int a=read(),b=read(),c=read();
lk[a].pb((edge){b,c});lk[b].pb((edge){a,c});
}
dfs(1,0,0);
dfs2(1,1);
seg::init(1,1,n);
while(m--)
{
x=read();w=read();
add_to_rt(x);
xs+=(ll)deep[x]*w;
s+=w;
x=q[seg::qiu(s+1>>1)];
write(xs+s*deep[x]-2*qiu_s(x));
}
fwrite(ch,1,now_w-ch+1,stdout);
}题目:https://www.luogu.org/problem/show?pid=1565
原题解似乎是 $O(n^3 * \log n)$ 的
但这题有$ O(n^3) $的做法。
虽然 https://www.luogu.org/record/show?rid=2494227 我这个$ O(n^3*\log n) $的做法跑的比我的$ O(n^3) $还快。。(应该是数据问题)
就是枚举上下边界$ x_1 $,$ x_2 $，然后枚举右端点 $ i $，
那么就是求最左的点 $ j $ 满足 $ sum_j < sum_i $ ( $ sum_i $ 表示 $ x=x_1...x_2,\,y=0...i $ 这个矩形的面积和)
如果 $ j_1 < j_2 $ 且 $ sum_{j_1} < sum_{j_2} $ ，那么 $j_2 $ 不可能成为左端点。
所以可以用单调栈维护可能的左端点，查询时二分。
$ O(n^3) $的做法:
(1) https://www.luogu.org/record/show?rid=2498503
枚举上下边界，实际上不只是可能的左端点在单调栈上，可以同理证明可能的右端点在相反的单调栈上。
从左到右枚举右端点(只枚举单调栈上的)，左端点的变化是单调的。于是可以$ O(n) $
(2) https://www.luogu.org/record/show?rid=2498807
感觉这是理论最快的做法。
原理是:当上下区间长度不变时 就是要求左右区间长度的最大值 $ mx $ , 而 $mx$ 最多变大 $ n $ 次。
长度从大到小地枚举上下边界(其实从小到大也一样)，再枚举右端点 $ i $ ，
如果以$i$为右端点的区间长度的最大值大于当前的$ mx $ ,那么 $ sum_i>min\,\, sum_j | j=[0,i-mx] $，这两者等价
所以维护这个$min$，如果发现$sum_i>min$，就++$ mx $，之后暴力重新$ O(n) $算出 $ min $。
如果上下区间长度从大到小枚举，其实长度不变或变小时都不用修改$mx$，于是最多重算$O(n)$次$min$。
从小到大枚举的话，当长度变大时需要将$mx$清0，于是最多重算$O(n^2)$次$min$。
总之总复杂度都是$O(n^3)$
#include<bits/stdc++.h>
using namespace std;
#define rep(i,l,r) for(int i=l;i<=r;++i)
template<class T>inline void chmax(T &x,const T &y)
{
if(x<y)x=y;
}
template<class T>inline void chmin(T &x,const T &y)
{
if(x>y)x=y;
}
typedef long long ll;
const int N=205;
ll s[N][N];
int ans;
ll a,_a;int w,_w;
#define get(y) (s[x2][y]-s[x1][y])
int main()
{
freopen("1.in","r",stdin);freopen("2.out","w",stdout);
int n,m;
cin>>n>>m;
rep(i,1,n)
{
rep(j,1,m)
{
scanf("%lld",s[i]+j);
s[i][j]+=s[i][j-1];
}
rep(j,1,m)
s[i][j]+=s[i-1][j];
}
int mx=1;
for(int t=n;t;--t)
{
int x1=0,x2=t;
do
{
int i=mx;ll mn=0;//mn=min(get(0)..get(i-mx))
do
{
chmin(mn,get(i-mx));
while(get(i)>mn&&mx<=i)
{++mx;
mn=0;
rep(j,1,i-mx) chmin(mn,get(j));
}
}while(++i<=m);
}while(++x1,++x2<=n);
chmax(ans,t*(mx-1));
}
printf("%d\n",ans);
}s是c的后缀，倒过来，s就是c的前缀。
之后建trie树，所有c就是s的子树。
所以问题就转化了求子树k大。
由于可以离线，所以可以把询问挂在节点上。
dfs一遍，用直接转移重儿子,暴力轻儿子的方法维护当前的权值线段树，时间O(nlog^2)。
有了权值线段树，询问时只用O(log)。
感觉会比主席树快，没试过。
加了fread,fwrite后拿了rank1
#include<bits/stdc++.h>
#define gc getchar()
int read()
{
char ch;
while((ch=gc)<'0');
int x=ch-'0';
while((ch=gc)>='0')x=x*10+ch-'0';
return x;
}
const int N=100005,T=300005;
int dy[N],j;
int ch[T][26],tot=1;
int cnt[T],t[T],next[N];
int sz[T],dfn[T],out[T],q[N],son[T];
int k[N],ans[N];
int a[N*3],d;
void clear(int i)
{
for(i+=d;i;i>>=1)--a[i];
}
void add(int i)
{
for(i+=d;i;i>>=1)++a[i];
}
#define L (i<<1)
int qiu(int k)
{
if(k>a[1]) return -1;
int i=1;
while(i<=d)
if(k<=a[L])i=L;
else { k-=a[L];i=L+1; }
return i-d;
}
char s[T];int len;
int to(int &x)
{
if(!x)x=++tot;
return x;
}
void dfs(int x)
{
dfn[x]=tot+1;
int i,y;
for(i=t[x];i;i=next[i]) q[++tot]=i;
for(i=0;i<26;++i)
if(y=ch[x][i])
{
dfs(y);
if(sz[y]>sz[son[x]]) son[x]=y;
}
sz[x]=(out[x]=tot)-dfn[x]+1;
}
void solve(int x)
{
int i,y,c=son[x];
if(sz[c])
{
for(i=0;i<26;++i)
if((y=ch[x][i])!=c&&sz[y])
{solve(y);
for(j=dfn[y];j<=out[y];++j) clear(q[j]);
}
solve(c);
for(j=dfn[x];j<dfn[c];++j) add(q[j]);
for(j=out[x];j>out[c];--j) add(q[j]);
}
else
for(j=dfn[x];j<=out[x];++j) add(q[j]);
for(j=0;j<cnt[x];++j)
{
i=q[dfn[x]+j];
ans[i]=qiu(k[i]);
}
}
int main()
{
int n=read(),i,now,x;
for(i=1;i<=n;++i)
{
scanf("%s",s+1);len=strlen(s+1);
now=1;
for(j=len;j;--j) now=to(ch[now][s[j]-'a']);
++cnt[dy[i]=now];
next[i]=t[now];t[now]=i;
}
for(i=1;i<=n;++i) k[i]=read();
for(d=1;d<n;d*=2);d-=1;
tot=0;
dfs(1);
solve(1);
for(i=1;i<=n;++i) printf("%d\n",ans[i]);
}点分，处理每个点到根的bitset，询问时或一下两个bitset。
但是由于可持久化树存储的bitset或运算会很慢，在q*n/32本来就是时间瓶颈的情况下显然是不好的，
所以我想不用可持久化bitset，而是直接每个点都新开个bitset。
注意到实际上bitset只用当前分治处理的这棵树的信息，所以离散化一下，大小就变成O(树的大小)了
于是复杂度就是O(n^2/32+n^2/2/32+..n^2/n/32)=O(n^2/32)。
于是我没有把int全部替换成unsigned short，也没有在分治的树小的时候暴力等等，就拿到了bzoj rank1。
#include<bits/stdc++.h>
using std::sort;
#define us unsigned short
#define ui unsigned int
const int N=40010;
struct edge
{
int to,next;
}l[N<<1];int e;
int a[N],t[N];
int n,i,x,y;
bool xiao(int *x,int *y)
{
return *x<*y;
}
void lisan()
{
static int *q[N],top;
for(i=1;i<=n;++i)q[i]=a+i;
sort(q+1,q+n+1,xiao);
int now=-1;
for(i=1;i<=n;++i)
{
if(*q[i]!=now){now=*q[i];++top;}
*q[i]=top;
}
}
us t_f[N],deep[N];
ui *b[17][N],**now_b,*X,*Y;
us U[N];
bool vis[N];
us q[N],head,tail,sz[N];
us cnt[N],mx;
us f[N];
void build(us rt,us dep,us fr)
{
for(;mx;--mx)cnt[mx]=0;
f[q[tail=1]=rt]=0;
for(head=1;head<=tail;++head)
{
x=q[head];sz[x]=1;
cnt[a[x]]=1;if(a[x]>mx)mx=a[x];
for(i=t[x];y=l[i].to;i=l[i].next)
if(!vis[y]&&y!=f[x])
f[q[++tail]=y]=x;
}
for(i=2;i<=mx;++i)cnt[i]+=cnt[i-1];
while(x=q[--head])
{
if((sz[x]<<1)>=tail)break;
sz[f[x]]+=sz[x];
}
rt=x;
t_f[rt]=fr;deep[rt]=dep;
vis[rt]=1;
now_b=b[dep];
f[q[tail=1]=rt]=0;
us u=(cnt[mx]>>5)+1; U[rt]=u;
for(head=1;head<=tail;++head)
{
x=q[head];a[x]=cnt[a[x]];
now_b[x]=new ui [u];
if(head>1) for(i=0;i<u;++i)now_b[x][i]=now_b[f[x]][i];
else for(i=0;i<u;++i)now_b[x][i]=0;
now_b[x][a[x]>>5]|=1<<(a[x]&31);
for(i=t[x];y=l[i].to;i=l[i].next)
if(!vis[y]&&y!=f[x])
{
f[y]=x;q[++tail]=y;
}
}
++dep;
for(int i=t[rt];y=l[i].to;i=l[i].next)
if(!vis[y]) build(y,dep,rt);
}
us get_lca(us x,us y)
{
while(x!=y)
if(deep[x]>deep[y])x=t_f[x];
else y=t_f[y];
return x;
}
namespace kcz
{
const int U=1<<16;
us f[U+1];
void init()
{
for(i=1;i<=U;++i)f[i]=f[i-(i&-i)]+1;
}
us count(ui x)
{
return f[x&(U-1)]+f[x>>16];
}
};
const int ch_top=5000000;
char ch[ch_top],*now_r=ch;
void read(int &x)
{
while(*now_r<'-')++now_r;
if(*now_r=='-')
{
for(x=*++now_r-'0';*++now_r>='0';) x=(x<<1)+(x<<3)+*now_r-'0';
x=-x;
}
else
{
for(x=*now_r-'0';*++now_r>='0';) x=(x<<1)+(x<<3)+*now_r-'0';
}
}
us ans;
int main()
{
freopen("1.in","r",stdin);freopen("1.out","w",stdout);
int q;
fread(ch,1,ch_top,stdin);
read(n);read(q);
for(i=1;i<=n;++i)read(a[i]);
lisan();
for(i=1;i<n;++i)
{
read(x);read(y);
l[++e]=(edge){y,t[x]};t[x]=e;
l[++e]=(edge){x,t[y]};t[y]=e;
}
build(1,0,0);
kcz::init();
while(q--)
{
read(x);read(y);//x=x^ans;
us lca=get_lca(x,y);
X=b[deep[lca]][x];Y=b[deep[lca]][y];
ans=0;
for(i=0;i<U[lca];++i) ans+=kcz::count(X[i]|Y[i]);
printf("%d\n",ans);
}
}首先二分答案ans, 平均数>=ans <=> 所有人-ans后,sum>=0
题目变成求长度在区间内的最长链
树形dp dp[i][j]表示i的子树里以i为top的长度为j的链max权值 枚举儿子即可转移 转移时顺便更新答案
注意到第一个儿子只用区间加上一个边的权值就可以直接转移 长链剖分 每条链开个线段树维护
O(nlog^2)
#include<bits/stdc++.h>
using std::max;
inline void chmax(double &x,const double &y) { if(x<y)x=y; }
const int N=100010;
const double minmin=1e-8;
int n,L,R;
int t[N];
struct edge
{
int to,next,len;
}l[N<<1];
int i,j,x,y,k;
int f[N],deep[N],mx[N],son[N],top[N],len_to_f[N];
struct seg
{
double *mx,*ad;
int n;
void init(int _n)
{
n=_n;
mx=new double [n*4+5];
ad=new double [n*4+5];
}
#define Mid (l+r>>1)
#define cl (k<<1)
#define cr (cl+1)
void add(int k,const double &w)
{
mx[k]+=w;ad[k]+=w;
}
void down(int k)
{
if(ad[k]) { add(cl,ad[k]);add(cr,ad[k]); }
ad[k]=0;
}
void up(int k)
{
mx[k]=max(mx[cl],mx[cr]);
}
void change(int x,const double &w)
{
int k=1,l=1,r=n;
while(l!=r)
{
down(k);
if(x<=Mid) { k=cl;r=Mid; }
else { k=cr;l=Mid+1; }
}
mx[k]=w;
while(k>>=1) up(k);
}
double ans;
int ql,qr;
void qiu(int k,int l,int r)
{
if(ql<=l&&qr>=r)
{
chmax(ans,mx[k]);
return ;
}
if(ql>r||qr<l) return ;
down(k);
qiu(cl,l,Mid);
qiu(cr,Mid+1,r);
}
double get(int l,int r)
{
ql=l;qr=r;ans=-1e12;
qiu(1,1,n);
return ans;
}
}a[N];
void init(int x)
{
for(y=x;y;y=son[y]) top[y]=x;
a[x].init(mx[x]);
}
int st[N],tail;
void dfs(int x,int fr=0,int Deep=0)
{
st[++tail]=x;
f[x]=fr;deep[x]=++Deep;
int i=t[x],y,i0,&c=son[x];
if(l[i].to==fr) { len_to_f[x]=l[i].len;i=t[x]=l[i].next;}
for(;y=l[i].to;i0=i,i=l[i].next)
if(y==fr)
{l[i0].next=l[i].next;len_to_f[x]=l[i].len;}
else
{
dfs(y,x,Deep);
if(mx[y]>mx[c]) c=y;
}
mx[x]=mx[c]+1;
if(!c) return ;
i=t[x];
if(l[i].to==c) i=t[x]=l[i].next;
for(;y=l[i].to;i0=i,i=l[i].next)
if(y==c) l[i0].next=l[i].next;
else init(y);
}
int head,del,rt;
bool ok(const double &base)
{
for(head=n;head;--head)
{
x=st[head];
seg &now=a[top[x]];
del=deep[x]-deep[top[x]]+1;
now.change(del,0);
for(i=t[x];y=l[i].to;i=l[i].next)
{
for(j=1;j<=a[y].n;++j)
if(a[y].get(j,j)+now.get(del+max(L-j,1),del+R-j)>=-minmin)
return 1;
for(j=1;j<=a[y].n;++j)
if(a[y].get(j,j)>=now.get(del+j,del+j)+minmin)
now.change(del+j,a[y].get(j,j));
}
if(now.get(del+L,del+R)>=-minmin) return 1;
now.add(1,len_to_f[x]-base);
}
return 0;
}
double erfen()
{
double l=0,r=1e6,mid;
for(int i=0;i<=40;++i)
if(ok(mid=(l+r)/2)) l=mid;
else r=mid;
return l;
}
int main()
{
freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d%d%d",&n,&L,&R);
int e=n;
for(i=1;i<n;++i,++e)
{
scanf("%d%d%d",&x,&y,&k);
l[i]=(edge){y,t[x],k};t[x]=i;
l[e]=(edge){x,t[y],k};t[y]=e;
}
dfs(1);init(1);
printf("%.3lf\n",erfen());
}题意:n*m的矩阵，有一些点不能选。k次操作，每次都让一个点变成不可选，每次都问当前可选的最大正方形。n,m,k<=2000
我想到了一个方法。过掉了。
新加的点造成的新的正方形一定过那个点，也就一定过它所在的列。
用第j列更新答案时，从当前答案+1开始从小到大试。 由于答案最多增加n次，所以总的尝试次数是O(N+K)的。 每次检验，我们从上到下枚举区间，用单调队列维护当前两边的最小值，时间是O(N)的。 所以总时间O(N^2+NK)
(看了cf的官方题解，没看懂，但时间是nklogk的)
但如果是求矩形最大面积怎么做呢？！！(或许不可做？)
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
void chmax(int &x,int y)
{
if(x<y)x=y;
}
#define N 2010
int l[N][N],r[N][N];//水平上延伸的极限点
bool ok[N][N];//可用的点
int now;
bool open;
int n,m,k,len,i,j;
void dp_lr(int i)//dp第i行的l,r
{
for (j=1;j<=m;++j)
if (ok[i][j])
l[i][j]=l[i][j-1];
for (j=m;j;--j)
if (ok[i][j])
r[i][j]=r[i][j+1];
}
struct queue
{
int q[N],h[N],head,tail;
void clear()
{
head=1;tail=0;
}
void push(int x)
{
while (tail>=head&&h[tail]>=x) --tail;
++tail;
q[tail]=i;h[tail]=x;
}
int len()
{
while (i-q[head]>now) ++head;
if (h[head]<0) return -N;
return h[head];
}
}ql,qr;
void dp_ud(int j)//第j列更新当前答案
{
for (;;)
{
ql.clear();qr.clear();
for (i=1;i<=now;++i)
{
ql.push(j-l[i][j]);
qr.push(r[i][j]-j);
}
for (;i<=n;++i)
{
ql.push(j-l[i][j]);
qr.push(r[i][j]-j);
if (ql.len()+qr.len()>=now) break;
}
if (i>n) return ;
++now;
}
}
char ch[N];
int o;
struct query
{
int x,y,ans;
void init()
{
scanf("%d%d",&x,&y);
ok[x][y]=0;l[x][y]=y+1;r[x][y]=y-1;
}
void add()
{
ans=now;
ok[x][y]=1;
dp_lr(x);
dp_ud(y);
}
}p[N];
int main()
{ freopen("1.in","r",stdin);freopen("1.out","w",stdout);
while (scanf("%d%d%d",&n,&m,&k)!=EOF)
{
int i,j;now=0;
for (i=1;i<=n;++i)
{
scanf("%s",ch+1);
for (j=1;j<=m;++j)
if(ch[j]=='.') ok[i][j]=1;
else { ok[i][j]=0;l[i][j]=j+1;r[i][j]=j-1; }
}
for (i=1;i<=k;++i) p[i].init();
for (i=1;i<=n;++i) {l[i][0]=1;r[i][m+1]=m;dp_lr(i);}
for (j=1;j<=m;++j) dp_ud(j);
for (i=k;i;--i)
p[i].add();
for (i=1;i<=k;++i) printf("%d\n",p[i].ans);
}
}
鄂公网安备 42010202000505 号Server time: 2025-08-11 18:30:17