loj2838 比太郎的聚会
题意大致就是给一张DAG，每次询问一个点和一个ban掉的点集，问除了这些点，剩下的点到询问点最长路的最大值。
简单维护根号个最远点，每次合并信息。
查询时直接暴力查表，如果表内一个都不行就重新计算一遍所有之前的点到这个点距离的最大值。
块大小调不好就会被卡常。
#include <bits/stdc++.h>
using namespace std;
const int N=100010;
const int M=200010;
const int Q=100010;
const int INF=2333333;
const int BLOCK=60;
void read(int &x){
char ch=getchar();
x=0;
while (ch<'0'||ch>'9') ch=getchar();
while (ch>='0'&&ch<='9') x=x*10+(ch&15),ch=getchar();
}
vector<pair<int,int> > f[N];
vector<int> id[N],ask[Q],rev[N];
bool Gmax(int &x,int y){
return x<y?(x=y,1):0;
}
int now[N],app[N];
void merge(int x){
//cerr<<"MERge"<<x<<endl;
for (auto j:rev[x]) now[j]=0;
while (f[x].size()<BLOCK){
int mx=-INT_MAX,ret=-1;
for (auto j:rev[x])
if (now[j]<f[j].size()&&Gmax(mx,f[j][now[j]].second)) ret=j;
if (ret==-1) break;
int id=f[ret][now[ret]].first;
if (app[id]==x) ++now[ret];
else{
app[id]=x;
f[x].emplace_back(f[ret][now[ret]++]);
}
}
for (auto &j:f[x]) ++j.second;
if (f[x].size()<BLOCK) f[x].emplace_back(make_pair(x,0));//add oneself
}
int ban[N],dis[N];
int bfs(int x,int fu){
//cerr<<"BFS"<<x<<" "<<fu<<endl;
for (int i=1; i<x; ++i) dis[i]=-INF;
dis[x]=0;
for (int i=x; i>=1; --i)
for (auto j:rev[i]) Gmax(dis[j],dis[i]+1);
int ret=-1;
for (int i=1; i<=x; ++i) if (ban[i]!=fu) Gmax(ret,dis[i]);
return ret;
}
int n,m,qq,ans[N];
int main(){
read(n); read(m); read(qq);
for (int i=1; i<=m; ++i){
int x,y; read(x); read(y);
rev[y].emplace_back(x);
}
for (int i=1; i<=qq; ++i){
int x,num; read(x);
id[x].emplace_back(i);
read(num);
ask[i].resize(num);
for (int j=0; j<num; ++j) read(ask[i][j]);
}
for (int x=1; x<=n; ++x){
merge(x);
for (auto i:id[x]){
for (auto j:ask[i]) ban[j]=i;
auto pos=f[x].begin(),ed=f[x].end();
for (; pos!=ed&&(ban[pos->first]==i); ++pos);
if (pos==ed) ans[i]=bfs(x,i);
else ans[i]=pos->second;
}
}
for (int i=1; i<=qq; ++i) cout<<ans[i]<<'
';
}
loj2397 幽深府邸
这题正解有点难，设(l(x))为左端第一把开(x)到(x+1)的锁的钥匙所在房间，(r(x))右端同理。
显然每个点可到一个区间，([L[x],R[x]])，那么怎么处理出这个区间呢，往左右交替跳。
这样如果从左往右扫，并且(i)想办法继承(i-1)，那么右端点单向移动且一次至少动(1)，左端点移动次数与右端点相同，复杂度就是(O(n))。
#include <bits/stdc++.h>
using namespace std;
const int N=500010;
vector<int> key[N];
int n,q,c[N],l[N],r[N],L[N],R[N],num[N],la[N];
int main(){
scanf("%d",&n);
for (int i=1; i<n; ++i) scanf("%d",&c[i]);
//cerr<<"END"<<endl;
for (int i=1; i<=n; ++i){
scanf("%d",&num[i]);
for (int j=1; j<=num[i]; ++j){
int x; scanf("%d",&x);
key[i].emplace_back(x);
}
}
//cerr<<"END2";
for (int i=1; i<=n; ++i){
for (auto j:key[i])
la[j]=i;
l[i]=la[c[i]];
}
for (int i=1; i<=n; ++i) la[i]=n+1;
for (int i=n; i>=1; --i){
for (auto j:key[i])
la[j]=i;
r[i]=la[c[i-1]];
}
R[n]=n;
for (int i=n-1; i>=1; --i){
if (l[i]<i){
R[i]=i;
continue;
}
R[i]=R[i+1];
while (R[i]<n&&l[R[i]]>=i) R[i]=R[R[i]+1];
}
//for (int i=1; i<=n; ++i) cerr<<i<<" "<<R[i]<<endl;
//return 0;
L[1]=1;
for (int i=2; i<=n; ++i){
if (r[i]>R[i]){
L[i]=i;
continue;
}
if (R[i-1]>=i){
L[i]=L[i-1];
R[i]=R[i-1];
continue;
}
L[i]=L[i-1];
while (1){
bool fl=0;
if (L[i]>1&&r[L[i]]<=R[i]){
fl=1;
L[i]=L[L[i]-1];
}
if (R[i]<n&&l[R[i]]>=L[i]){
fl=1;
R[i]=R[R[i]+1];
}
if (!fl) break;
}
//cerr<<i<<" "<<L[i]<<" "<<R[i]<<endl;
//return 0;
}
//for (int i=1; i<=n; ++i) cerr<<L[i]<<" "<<R[i]<<endl;
//cerr<<"UP";
scanf("%d",&q);
//cerr<<"FUCK";
for (int i=1; i<=q; ++i){
int x,y; scanf("%d%d",&x,&y);
cout<<(L[x]<=y&&y<=R[x]?"YES
":"NO
");
}
}
考试时打的未知复杂度算法，获得运行时间最后一名。
#include <bits/stdc++.h>
using namespace std;
typedef long long lo;
const int N=500010;
const int NUM=625;
bitset<N> b[NUM+5];
int kil[N],tot,c[N],*f[N],num[N],C[N],ll[N],rr[N];
int n,q,ups;
void read(int &x){
char ch=getchar();
x=0;
while (ch<'0'||ch>'9') ch=getchar();
while (ch>='0'&&ch<='9') x=x*10+(ch&15),ch=getchar();
}
void work(int x,int y){
//cerr<<"WORK"<<x<<" "<<y<<endl;
bitset<N> &g=b[y];
for (int i=1; i<=num[x]; ++i) g.set(f[x][i]);
//for (int i=1; i<=num[x]; ++i) cerr<<"X"<<f[x][i]<<endl;
int l=x,r=x;
bool fl;
do{
fl=0;
while (g[C[l-1]]){
fl=1;
--l;
for (int i=1; i<=num[l]; ++i) g.set(f[l][i]);
}
while (g[C[r]]){
fl=1;
++r;
for (int i=1; i<=num[r]; ++i) g.set(f[r][i]);
}
//cerr<<l<<" "<<r<<endl;
}while (fl);
ll[x]=l; rr[x]=r;
//for (int i=1; i<=n; ++i) cerr<<g[i]; cerr<<endl;
}
vector<bitset<N>*> op;
inline bool test(int x){
for (auto i:op)
if (i->test(x)) return 1;
return 0;
}
void work2(int x){
//cerr<<"WORK2"<<x<<endl;
bitset<N> g; op.clear();
for (int i=1; i<=num[x]; ++i) g.set(f[x][i]);
int l=x,r=x;
bool fl;
do{
fl=0;
while (g[C[l-1]]||test(C[l-1])){
fl=1;
--l;
if (kil[l]){
//cerr<<"LL"<<l<<" "<<x<<endl;
//g|=b[kil[l]];
op.push_back(&b[kil[l]]);
l=ll[l];
r=max(r,rr[l]);
//cerr<<"AT"<<l<<" "<<r<<endl;
}
else for (int i=1; i<=num[l]; ++i) g.set(f[l][i]);
}
while (g[C[r]]||test(C[r])){
fl=1;
++r;
if (kil[r]){
//cerr<<"LL"<<l<<" "<<r<<" "<<x<<endl;
//g|=b[kil[r]];
op.push_back(&b[kil[r]]);
l=min(l,ll[r]);
r=rr[r];
//cerr<<"AT"<<l<<" "<<r<<endl;
}
else for (int i=1; i<=num[r]; ++i) g.set(f[r][i]);
}
//cerr<<l<<" "<<r<<endl;
//for (int i=1; i<=n; ++i) cerr<<g[i]; cerr<<endl;
}while (fl);
ll[x]=l; rr[x]=r;
}
int main(){
scanf("%d",&n);
//cerr<<"N"<<n<<endl;
for (int i=1; i<n; ++i) scanf("%d",&C[i]);
//for (int i=1; i<n; ++i) cerr<<C[i]<<' ';
for (int i=1; i<=n; ++i){
//read(num[i]);
scanf("%d",&num[i]);
//cerr<<"ups"<<num[i]<<endl;
f[i]=&c[tot];
for (int j=1; j<=num[i]; ++j) scanf("%d",&c[++tot]);
}
lo sum=0;
for (int i=1; i<=n; ++i) sum+=num[i];
double sz=(double)sum/NUM;
sum=0;
for (int i=1; i<=n; ++i){
sum+=num[i];
if (sum>=sz){
kil[i]=++ups;
sum=0;
}
}
//cerr<<"ups"<<ups<<endl;
for (int i=1; i<=n; ++i) if (kil[i]) work(i,kil[i]);
for (int i=1; i<=n; ++i) if (!kil[i]) work2(i);
//for (int i=1; i<=n; ++i) cerr<<ll[i]<<" "<<rr[i]<<endl;
//return 0;
//read(q);
scanf("%d",&q);
//cerr<<"Q"<<q<<endl;
for (int i=1; i<=q; ++i){
int x,y;
scanf("%d%d",&x,&y);
cout<<(ll[x]<=y&&y<=rr[x]?"YES
":"NO
");
}
}
loj2393门票安排
这题神仙题。
先破环成链。
再证明翻转的区间两两有交，即翻转区间集合有公共交。
二分答案ans
再证明包含原方案最大值的区间必有ans或ans-1个不翻。
因为翻了两个就不优了。
最大值如果有多个，就随便取一个，感性理解一下就是编号在环上本来就没有意义。
然后就没了。
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef pair<pair<int,int>,int> pii;
priority_queue<pii> q;
const int N=200010;
int a[N],b[N],c[N];
vector<int> g[N];
int cf[N],original[N];
int n,m;
bool check(int k,ll lim,ll all){
if (original[k]-all>lim) return 0;
//cerr<<"CHcK"<<k<<" "<<lim<<" "<<all<<" "<<original[k]<<endl;
while (!q.empty()) q.pop();
for (int i=1; i<=n; ++i) cf[i]=0,g[i].clear();
for (int i=1; i<=m; ++i)
if (a[i]<=k&&k<b[i]){
g[a[i]].push_back(i);
}
//cerr<<"@@##"<<endl;
int used=0;
for (int i=1; i<=k; ++i){
ll tmp=max((original[i]-used+all-used)-lim,0ll);
tmp=(tmp+1)/2;
for (auto j:g[i]) q.push(make_pair(make_pair(b[j],j),c[j]));
while (tmp&&!q.empty()){
pii x=q.top(); q.pop();
int it=min(x.second,tmp);
//cerr<<"REV"<<x.first.second<<endl;
tmp-=it;
cf[a[x.first.second]]-=it;
cf[b[x.first.second]]+=it*2;
used+=it;
x.second-=it;
if (x.second) q.push(x);
}
//cerr<<"I"<<i<<" "<<tmp<<" "<<k<<endl;
//getchar();
if (tmp) return 0;
}
//cerr<<"???";
//for (int i=1; i<=n; ++i) cerr<<cf[i]<<" "; cerr<<endl;
for (int i=1; i<=n; ++i){
cf[i]+=cf[i-1];
if (i>k&&cf[i]+original[i]>lim) return 0;
}
return 1;
}
bool Gmax(int &x,int y){
return x<y?(x=y,1):0;
}
signed main(){
scanf("%lld%lld",&n,&m);
for (int i=1; i<=m; ++i){
scanf("%lld%lld%lld",&a[i],&b[i],&c[i]);
if (a[i]>b[i]) swap(a[i],b[i]);
}
for (int i=1; i<=m; ++i){
original[a[i]]+=c[i];
original[b[i]]-=c[i];
}
for (int i=1; i<=n; ++i){
original[i]+=original[i-1];
}
ll mx=-LLONG_MAX,ret;
for (int i=1; i<=n; ++i) if (Gmax(mx,original[i])) ret=i;
//cerr<<"@@###"<<ret<<endl;
int ans=-1;
for (int l=0,r=LLONG_MAX/10,mid=(l+r)>>1; l<=r; mid=(l+r)>>1)
if (check(ret,mid,original[ret]-mid)||check(ret,mid,original[ret]-mid+1)) ans=mid,r=mid-1; else l=mid+1;
cout<<ans;
}