线段树好啊
2024-06-30 09:38:38
发布于:上海
16阅读
0回复
0点赞
区间修改单点查询,显然可以用线段树做啊。
注意给的是端点位置,所以你可能需要把平板作为左开右闭区间处理。样例还是挺良心的,让你发现了这个细节,至少不会 WA 声一片。
当然树状数组也是可以的。
思路:开局直接离线下来,按高度排序,从低到高依次计算,时间复杂度 。
#include <cstdio>
#include <algorithm>
using namespace std;
#define MAXN 10000
#define m(l,r) ((l+r)>>1)
#define ls(k) (k<<1)
#define rs(k) ((k<<1)|1)
struct node{
int l,r,dat,tag;
}t[4*MAXN+5];
void build(int p, int l, int r){
t[p].l=l;
t[p].r=r;
t[p].tag=0;
if(l==r){t[p].dat=0; return;}
int mid=m(l,r);
build(ls(p),l,mid);
build(rs(p),mid+1,r);
t[p].dat=0;
}
inline void down(int p){
if(t[p].tag){
t[ls(p)].dat=t[p].tag;
t[rs(p)].dat=t[p].tag;
t[ls(p)].tag=t[p].tag;
t[rs(p)].tag=t[p].tag;
t[p].tag=0;
}
}
void change(int p,int x,int y,int z){
if(x<=t[p].l && y>=t[p].r){
t[p].dat=z;
t[p].tag=z;
return;
}
down(p);
int mid=m(t[p].l,t[p].r);
if(x<=mid) change(ls(p),x,y,z);
if(y>mid) change(rs(p),x,y,z);
}
int ask(int p,int x){
if(x==t[p].l && x==t[p].r) return t[p].dat;
down(p);
int mid=m(t[p].l,t[p].r);
if(x<=mid) return ask(ls(p),x);
else return ask(rs(p),x);
}
inline int read(){
int x=0;
bool w=0;
char ch=getchar();
while(ch<'0'||ch>'9') ch=='-'&&(w=1),ch=getchar();
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return w?-x:x;
}
void write(int x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar((x%10)|48);
}
struct tb{
int l,r,h;
}a[105];
inline bool cmp(tb x,tb y){return x.h<y.h;}
int main(){
int n=read();
build(1,1,10000);
for(int i=1;i<=n;i++) a[i].h=read(),a[i].l=read(),a[i].r=read();
sort(a+1,a+1+n,cmp);
int ans=0;
for(int i=1;i<=n;i++){
ans+=a[i].h-ask(1,a[i].l);
ans+=a[i].h-ask(1,a[i].r-1);
change(1,a[i].l,a[i].r-1,a[i].h);
}
write(ans);
return 0;
}
这里空空如也
有帮助,赞一个