就是线段树维护区间的最小值 但是要注意 本题坑人的地方 是 a到b站 实际上是维护a到b-1 因为b站已经下车了 我勒个去呀
#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<algorithm>
#define lson rt<<1
#define rson rt<<1|1
#define getmid int mid=(l+r)/2
using namespace std;
const int maxn=; int n,m,k,mins[maxn*],tag[maxn*]; void pushdown(int rt)
{
if(tag[rt]!=)
{
mins[rt]+=tag[rt];
tag[lson]+=tag[rt];
tag[rson]+=tag[rt];
tag[rt]=;
}
} void bud(int l,int r,int rt)
{
if(l==r) {
mins[rt]=m;
return;
}
getmid;
bud(l,mid,lson);
bud(mid+,r,rson);
mins[rt]=min(mins[lson],mins[rson]);
} int query(int l,int r,int rt,int a,int b)
{
pushdown(rt);
if(a<=l && b>=r)
{
return mins[rt];
}
getmid;
int ans=<<;
if(a<=mid) ans=query(l,mid,lson,a,b);
if(b>mid) ans=min(ans,query(mid+,r,rson,a,b));
return ans;
} void update(int l,int r,int rt,int a,int b,int c)
{
pushdown(rt);
if(a<=l && b>=r)
{
tag[rt]+=c;
return;
}
getmid;
if(a<=mid) update(l,mid,lson,a,b,c);
if(b>mid) update(mid+,r,rson,a,b,c); mins[rt]=min(mins[lson]+tag[lson],mins[rson]+tag[rson]); } int main()
{
scanf("%d%d%d",&n,&m,&k);
bud(,n,); for(int i=,a,b,c;i<=k;i++)
{
scanf("%d%d%d",&a,&b,&c);
int tt=query(,n,,a,b-);
if(tt>=c)
{
printf("T\n");
update(,n,,a,b-,-c);
}
else
{
printf("N\n");
}
}
return ;
}