八月空飄下了雪花 魚(yú)飛滿天鳥(niǎo)在水下 貓被鼠啃食到骨架 我是誰(shuí)得不到回答
test27
螃蟹在剝我的殼pangxie
二分答案，然后用堆模擬即可。
#include<bits/stdc++.h>
#define int long long
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)
#define mp make_pair
using namespace std;
const int N=1000005;
int n, T, d[N];
priority_queue<int,vector<int>,greater<int> > q;
bool check(int k) {
up(i,1,k) q.push(d[i]);
int ret=0, i=k+1;
while(q.size()) {
ret=q.top(), q.pop();
if(i<=n) q.push(ret+d[i]), ++i;
}
return ret<=T;
}
signed main() {
freopen("pangxie.in","r",stdin);
freopen("pangxie.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> T;
up(i,1,n) cin >> d[i];
int l=1, r=n, ans;
while(l<=r) {
int mid=(l+r)>>1;
if(check(mid)) ans=mid, r=mid-1;
else l=mid+1;
}
cout << ans << '\n';
return 0;
}
筆記本在寫(xiě)我bijiben
離線排序加入右端點(diǎn)，以值為下標(biāo)建立位置最大值的線段樹(shù)，查詢就是找 \(<l\) 的最小位置。
#include<bits/stdc++.h>
#define int long long
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
using namespace std;
const int N=200005, inf=1e9;
int n, m, a[N], Ans[N], tr[N<<2];
vector<pii> Q[N];
void updata(int x,int v,int p=1,int s=1,int e=n+1) {
if(s==e) { tr[p]=max(tr[p],v); return; }
int mid=(s+e)>>1;
if(x<=mid) updata(x,v,ls(p),s,mid);
if(x>mid) updata(x,v,rs(p),mid+1,e);
tr[p]=min(tr[ls(p)],tr[rs(p)]);
}
int query(int v,int p=1,int s=1,int e=n+1) {
if(s==e) return s;
int mid=(s+e)>>1;
if(tr[ls(p)]<v) return query(v,ls(p),s,mid);
return query(v,rs(p),mid+1,e);
}
signed main() {
freopen("bijiben.in","r",stdin);
freopen("bijiben.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
up(i,1,n) cin >> a[i], ++a[i];
up(i,1,m) {
int l, r;
cin >> l >> r;
Q[r].pb(mp(l,i));
}
up(i,1,n) {
if(a[i]<=n+1) updata(a[i],i);
for(pii p:Q[i]) {
int id=p.second, l=p.first;
Ans[id]=query(l)-1;
}
}
up(i,1,m) cout << Ans[i] << '\n';
return 0;
}
漫天的我落在楓葉上雪花上x(chóng)uehua
正解有點(diǎn)像常數(shù)劣化是可以說(shuō)的嗎（？
關(guān)心 \(s,w(s),ans,t\)，考慮 \(j\to i\) 條件有什么（
- \(s_j\subseteq s_i\)
- \(t_j<t_i\)
- \(w(s_i/s_j)\leq w\) 或者說(shuō) \(w(s_j)-w(s_i)\leq w\)
如果只有限制 \(1\) 那么可以考慮的方向有高維前綴和形狀的 dp 或者拆二進(jìn)制數(shù)平衡復(fù)雜度，但是前者放在這題好像不太可行，因?yàn)槟悴荒馨?\(w(s)\) 或者 \(ans\) 塞進(jìn)狀態(tài)，而這種二維的信息沒(méi)有偏序關(guān)系，這個(gè)前提下做子集枚舉和暴力沒(méi)有區(qū)別。考慮后者，還要處理掉二維偏序，不妨考慮 cdq 分治，進(jìn)行一個(gè)常數(shù)的劣化。
#include<bits/stdc++.h>
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)
using namespace std;
const int N=19, M=100005;
int n, m, w, b[N], sw[1<<N], msk[M], v[M], f[M], Ans, g[1<<N];
signed main() {
freopen("xuehua.in","r",stdin);
freopen("xuehua.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> w;
up(i,1,n) cin >> b[i];
up(s,1,(1<<n)-1) up(i,1,n) if(s>>(i-1)&1) sw[s]+=b[i];
up(i,1,m) {
int len, tmp;
cin >> v[i] >> len;
while(len--) cin >> tmp, msk[i]|=1<<(tmp-1);
f[i]=v[i];
if(m<=1e3) {
up(j,1,i-1) if((msk[i]|msk[j])==msk[i]&&sw[msk[i]^msk[j]]<=w) {
f[i]=max(f[i],f[j]+v[i]);
}
}
else {
for(int s=msk[i]; s; s=(s-1)&msk[i]) if((msk[i]|s)==msk[i]&&sw[msk[i]^s]<=w) {
f[i]=max(f[i],g[s]+v[i]);
}
g[msk[i]]=max(g[msk[i]],f[i]);
}
Ans=max(Ans,f[i]);
}
cout << Ans << '\n';
return 0;
}
而你在想我xiangni
分塊維護(hù) deque 就行了。
#define _CRT_SECURE_NO_WARNINGS
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include<bits/stdc++.h>
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)
using namespace std;
const int N=100005, M=320, mod=600;
int n, B, q, a[N], cnt[M][N], sp[N], tot, xo;
struct base {
int L=1e5+1, R=1e5, cnt[N], val[4*M];
void build(int l,int r) {
// cout << "build " << l << ' ' << r << '\n';
up(i,l,r) val[(++R)%mod]=a[i], ++cnt[a[i]];
}
int pushr(int len,int ran) {
dn(i,R,R-len+1) val[(i+1)%mod]=val[(i)%mod];
val[(R-len+1)%mod]=ran;
++cnt[ran], --cnt[val[(R+1)%mod]];
return val[(R+1)%mod];
}
void pushl(int len,int ran) {
++cnt[ran], --cnt[val[(L+len-1)%mod]];
dn(i,L+len-1,L+1) val[(i)%mod]=val[(i-1)%mod];
val[(L)%mod]=ran;
}
int move(int ran) {
val[(--L)%mod]=ran;
++cnt[ran], --cnt[val[(R)%mod]];
return val[(R--)%mod];
}
int get(int l,int r,int x) {
int ret=0;
up(i,l,r) ret+=val[(L+i-1)%mod]==x;
return ret;
}
int ranger(int x) {
return val[(L+x-1)%mod];
}
void restore(int l,int r) {
int lst=val[(L+r-1)%mod];
dn(i,r-1,l) val[(L+i)%mod]=val[(L+i-1)%mod];
val[(L+l-1)%mod]=lst;
}
} qwq[M];
//void check() {
// cout << "a = ";
// int T=(n+B-1)/B;
// up(u,1,T) {
// cout << '[';
// up(i,qwq[u].L,qwq[u].R) {
// cout << qwq[u].val[i] << ' ';
// }
// cout << ']';
// } cout << '\n';
//}
signed main() {
freopen("xiangni.in","r",stdin);
freopen("xiangni.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n, B=sqrt(n);
up(i,1,n) cin >> a[i], sp[++tot]=a[i];
sort(sp+1,sp+1+tot), tot=unique(sp+1,sp+1+tot)-sp-1;
up(i,1,n) a[i]=lower_bound(sp+1,sp+1+tot,a[i])-sp;
up(i,1,(n+B-1)/B) qwq[i].build((i-1)*B+1,min(i*B,n));
// check();
cin >> q;
while(q--) {
int opt, l, r, val, k;
cin >> opt >> l >> r;
l=(l+xo-1)%n+1, r=(r+xo-1)%n+1;
if(r<l) swap(l,r);
if(opt==1) {
int L=(l+B-1)/B, R=(r+B-1)/B;
// cout << "updata/ " << l << ' ' << r << '\n';
if(L==R) {
qwq[L].restore(l-(L-1)*B,r-(L-1)*B);
}
else {
int lst=qwq[L].pushr(L*B-l+1,qwq[R].ranger(r-(R-1)*B));
up(i,L+1,R-1) lst=qwq[i].move(lst);
qwq[R].pushl(r-(R-1)*B,lst);
}
// check();
}
else {
cin >> val;
k=lower_bound(sp+1,sp+1+tot,val)-sp;
if(sp[k]!=val) {
xo=0;
cout << 0 << '\n';
continue;
}
int L=(l+B-1)/B, R=(r+B-1)/B, Ans=0;
if(L==R) {
Ans=qwq[L].get(l-(L-1)*B,r-(L-1)*B,k);
}
else {
up(i,L+1,R-1) Ans+=qwq[i].cnt[k];
Ans+=qwq[L].get(l-(L-1)*B,B,k);
Ans+=qwq[R].get(1,r-(R-1)*B,k);
}
cout << Ans << '\n';
xo=Ans;
// cout << "Q " << l << ' ' << r << ' ' << k << ' ' << Ans << '\n';
}
}
return 0;
}
浙公網(wǎng)安備 33010602011771號(hào)