• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

Recommended Posts




我们问一个小矩形最多能框住多少颗星,也就是这个区间的最大值是多少。因为小矩形移动过程中要保持区间的最大值,所以我们可以选择用线段树来保持区间的最大值。我们按照星星的纵坐标建树,还要按照横坐标把星星从小到大排序,这样只有把纵坐标离散化后,才能按照横坐标从左到右扫描。求一个区间内恒星的亮度,可以用差来思考,把它的亮度加到这个区间的左边界(即以\(x\)对应的\(y,y h\)边为横坐标),再从右边界减去它的亮度。这样我们就能知道区间的值是多少。



使用i64=long long

#定义rep(i,a,n)for(int I=a;I n;我)

#define per(i,a,n)for(int I=n-1;I=a;我-)

#define SZ(a) (int(a.size()))


#定义所有(a) a.begin(),a.end()


constexpr int N=10010


int l,r;

i64 val,标签;

} tr[N 3];


int x,y1,y2;


布尔运算符(const Star W) const {

if (x==W.x)返回w W.w

返回x W.x


} seg[N2];

void pushup(int u) {

trval=std:max(tr[u 1])。val,tr[u 1 | 1]。val) tr。标签;


void build(int u,int l,int r) {

tr={l,r,0,0 };

if (l==r)返回;

int mid=l r 1;

build(u 1,l,mid),build(u 1 | 1,mid 1,r);



void modify(int u,int l,int r,i64 val) {

if (tr)。l=l tr。r=r) {





int mid=(tr)。l tr。r)1;

if (mid=l) modify(u 1,l,r,val);

if (mid r) modify(u 1 | 1,l,r,val);



void solve() {

int n,w,h;scanf('%d%d%d ',n,w,h);

STD : vector ys;

for (int i=1,j=0;I=n;i ) {

int x,y;

i64 val

scanf('%d%d%lld ',x,y,val);

seg[j ]={x,y,y h,val };

seg[j ]={x w,y,y h,-val };

ys.pb(y),ys . Pb(y h);


std:sort(ys.begin()、ys . end());

ys . erase(STD : unique(ys . begin(),ys.end()),ys . end());

build(1,0,int(ys . size())-1);

std:sort(seg,seg 2 * n);

i64 ans=0;

自动查找=[] (int x) - int {

返回STD : lower _ bound(ys . begin(),ys.end(),x)-ys . begin();


for(int I=0;I n * 2;i ) {

修改(1,查找(seg.y1),查找(seg.y2) - 1,seg.w);



printf('%lld\n ',ans);


int main() {

int t;scanf('%d ',t);




Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now