关于O2
  • 板块P2184 贪婪大陆
  • 楼主Daidly
  • 当前回复12
  • 已保存回复12
  • 发布时间2021/9/2 11:58
  • 上次更新2023/11/4 08:09:01
查看原帖
关于O2
271736
Daidly楼主2021/9/2 11:58

就是这道题,我提交这个代码:

#include<bits/stdc++.h>
using namespace std;
#define ls p<<1
#define rs p<<1|1

inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

inline void print(int x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)print(x/10);
	putchar(x%10^48);
}

const int MAXN=1e5+5;
int n,m,a[MAXN];
struct node{
	int w;
}tl[MAXN<<2],tr[MAXN<<2];

void push_up_l(int p){
	tl[p].w=tl[ls].w+tl[rs].w;
}

void push_up_r(int p){
	tr[p].w=tr[ls].w+tr[rs].w;
}

void modify_l(int l,int r,int pos,int p){
	if(l==r){
		tl[p].w++;
		return;
	}
	int mid=l+r>>1;
	if(pos<=mid)modify_l(l,mid,pos,ls);
	if(mid<pos)modify_l(mid+1,r,pos,rs);
	push_up_l(p);
}

void modify_r(int l,int r,int pos,int p){
	if(l==r){
		tr[p].w++;
		return;
	}
	int mid=l+r>>1;
	if(pos<=mid)modify_r(l,mid,pos,ls);
	if(mid<pos)modify_r(mid+1,r,pos,rs);
	push_up_r(p);
}

int query_l(int l,int r,int lq,int rq,int p){
	if(lq<=l&&r<=rq)return tl[p].w;
	int mid=l+r>>1,sum=0;
	if(lq<=mid)sum+=query_l(l,mid,lq,rq,ls);
	if(mid<rq)sum+=query_l(mid+1,r,lq,rq,rs);
	return sum;
}

int query_r(int l,int r,int lq,int rq,int p){
	if(lq<=l&&r<=rq)return tr[p].w;
	int mid=l+r>>1,sum=0;
	if(lq<=mid)sum+=query_r(l,mid,lq,rq,ls);
	if(mid<rq)sum+=query_r(mid+1,r,lq,rq,rs);
	return sum;
}

signed main(){
	n=read();
	int opt,l,r,num,numl,numr;
	m=read();
	while(m--){
		opt=read(),l=read(),r=read();
		if(opt==1){
			num++;
			modify_r(1,n,r,1);
			modify_l(1,n,l,1);
		}else{
			if(l==1)numl=0;
			else numl=query_r(1,n,1,l-1,1);
			if(r==n)numr=0;
			else numr=query_l(1,n,r+1,n,1);
			print(num-numl-numr),puts("");
		}
	}
	return 0;
}

开O2之后全WA,然后我就没开,就过了,有dalao能帮忙解释一下吗

2021/9/2 11:58
加载中...