社区讨论
为什么我的块长是200?
P5356[Ynoi Easy Round 2017] 由乃打扑克参与者 2已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @lo23v4pj
- 此快照首次捕获于
- 2023/10/23 07:34 2 年前
- 此快照最后确认于
- 2023/11/03 07:54 2 年前
TLE了无数回,直到把块长从 调成200。求助。
CPP#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=1e5+10,BUFSIZE=1<<20,B=6000,inf=2147483647;
int n,m,T,block,tag[B],pos[N],L[B],R[B];
struct node{
int val,id;
}a[N];
char ibuf[BUFSIZE],*is=ibuf,*it=ibuf;
char getch(){
if(is==it)
it=(is=ibuf)+fread(ibuf,1,BUFSIZE,stdin);
return is==it?EOF:*is++;
}
int read(){
int x=0,f=1;char ch=getch();
while(ch<'0'||ch>'9') ch=getch();
while(ch>='0'&&ch<='9')
{x=(x<<1)+(x<<3)+(ch^48);ch=getch();}
return x*f;
}
bool cmp(node x,node y){
if(x.val!=y.val) return x.val<y.val;
else return x.id<y.id;
}
int min(int x,int y){
return x<y?x:y;
}
int max(int x,int y){
return x>y?x:y;
}
void change(int l,int r,int k){
int lp=pos[l],rp=pos[r];
if(lp==rp){
for(int i=L[lp];i<=R[lp];++i)
if(a[i].id>=l&&a[i].id<=r) a[i].val+=k;
sort(a+L[lp],a+1+R[lp],cmp);
}
else{
for(int i=L[lp];i<=R[lp];++i) if(a[i].id>=l) a[i].val+=k;
for(int i=L[rp];i<=R[rp];++i) if(a[i].id<=r) a[i].val+=k;
sort(a+L[lp],a+1+R[lp],cmp);sort(a+L[rp],a+1+R[rp],cmp);
for(int i=lp+1;i<=rp-1;++i) tag[i]+=k;
}
}
int ask(int l,int r,int k){
int lp=pos[l],rp=pos[r],res=0;
if(lp==rp){
for(int i=L[lp];i<=R[lp];++i)
if(a[i].id>=l&&a[i].id<=r) res+=(a[i].val+tag[lp])<=k;
}
else{
for(int i=L[lp];i<=R[lp]&&a[i].val+tag[lp]<=k;++i) if(a[i].id>=l) ++res;
for(int i=L[rp];i<=R[rp]&&a[i].val+tag[rp]<=k;++i) if(a[i].id<=r) ++res;
for(int i=lp+1;i<=rp-1;++i){
if(a[R[i]].val+tag[i]<=k) res+=R[i]-L[i]+1;
else if(a[L[i]].val+tag[i]<=k){
int h=lower_bound(a+L[i],a+R[i]+1,(node){k-tag[i],100005},cmp)-a-1;
res+=h-L[i]+1;
}
}
}
return res;
}
int gmin(int l,int r){
int lp=pos[l],rp=pos[r],minn=inf;
if(lp==rp){
for(int i=L[lp];i<=R[rp];++i)if(a[i].id<=r&&a[i].id>=l){
minn=a[i].val+tag[lp];break;
}
}
else{
for(int i=L[lp];i<=R[lp];++i) if(a[i].id>=l) {minn=min(minn,a[i].val+tag[lp]);break;}
for(int i=L[rp];i<=R[rp];++i) if(a[i].id<=r) {minn=min(minn,a[i].val+tag[rp]);break;}
for(int i=lp+1;i<=rp-1;++i) minn=min(minn,a[L[i]].val+tag[i]);
}
return minn;
}
int gmax(int l,int r){
int lp=pos[l],rp=pos[r],maxx=-inf;
if(lp==rp){
for(int i=R[lp];i>=L[lp];i--)if(a[i].id>=l&&a[i].id<=r){
maxx=max(maxx,a[i].val+tag[lp]);break;
}
}
else{
for(int i=R[lp];i>=L[lp];i--) if(a[i].id>=l) {maxx=max(maxx,a[i].val+tag[lp]);break;}
for(int i=R[rp];i>=L[rp];i--) if(a[i].id<=r) {maxx=max(maxx,a[i].val+tag[rp]);break;}
for(int i=lp+1;i<=rp-1;++i) maxx=max(maxx,a[R[i]].val+tag[i]);
}
return maxx;
}
void query(int ql,int qr,int k){
int l=gmin(ql,qr),r=gmax(ql,qr),ans;
while(l<=r){
int mid=(l+1)/2+r/2;
int p=ask(ql,qr,mid);
if(p>=k) r=mid-1,ans=mid;
else l=mid+1;
}
printf("%d\n",ans);
}
int main(){
n=read();m=read();
T=200;
block=n/T+(n%T!=0);
for(int i=1;i<=n;++i) a[i].val=read(),a[i].id=i;
for(int i=1;i<=block;++i){
L[i]=(i-1)*T+1;
R[i]=i*T;if(i==block) R[i]=n;
for(int j=L[i];j<=R[i];j++) pos[j]=i;
}
for(int i=1;i<=block;++i) sort(a+L[i],a+1+R[i],cmp);
int op,ll,rr,kk;
while(m--){
op=read();ll=read();rr=read();kk=read();
if(op==1){
if(rr-ll+1<kk) puts("-1");
else query(ll,rr,kk);
}
else{
change(ll,rr,kk);
}
}
return 0;
}
回复
共 1 条回复,欢迎继续交流。
正在加载回复...