社区讨论

为什么我的块长是200?

P5356[Ynoi Easy Round 2017] 由乃打扑克参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@lo23v4pj
此快照首次捕获于
2023/10/23 07:34
2 年前
此快照最后确认于
2023/11/03 07:54
2 年前
查看原帖
TLE了无数回,直到把块长从 n×logn\sqrt{n} \times log{n} 调成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 条回复,欢迎继续交流。

正在加载回复...