自动搬运

查看原文

来自洛谷，原作者为

	Konnyaku_ljc .

搬运于2025-08-24 22:05:47，当前版本为作者最后更新于2019-09-12 00:21:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

线段树（较简略）+模拟（最短但是没注释）

要不是和我老婆有关，我才不做呢（哼

这道题我一年前就发现了，模拟45pt，看到模拟题解后，我吃了一惊。。。为什么倒序循环能ACCEPT，而正序只有45pt？！自闭了
所以我吸氧的36行跑的那么快仅仅就改了个倒序循环。。。
几个坑点

• 飞鱼丸会吸走能量，但是bcy只能获得飞鱼丸吸收后的能量
• 让您以为本题是线段树，做完之后再告诉您其实是个暴力。。。
• 没玩过bh3也能做
• 嘤嘤刀不会升级

但我们还是要来说一下线段树，其实线段树真的不好码。。。
因为我们不但要标记飞鱼丸，还有区间修改，最大值查询和单点修改

我找了好几道线段树才拼在一起的！

解释不多，相信您们都能看懂，我码了2个小时，12点啦，虚啦~

变量名有一半是我老婆哦！！！

#include <iostream>
#include <cstdio>
using namespace std;
int n,m,bcy=0,p,x,y,v;
//布狼牙/八重樱/琪亚娜
int blny[100000+100],qyn[100000*4+10];
//因为重载了max,所以延迟标记要单独出来
struct node{
    int maxx,max_place;
    friend node max(node a,node b) { return a.maxx>b.maxx ? a:b; }//重载max
}tree[100000*4+10];//存树 
void build(int l,int r,int num) // 标准建树 
{
    if(l==r)
	{
        cin >> tree[num].maxx;
        tree[num].max_place=l; 
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,num<<1);
    build(mid+1,r,num<<1|1);
    tree[num]=max(tree[num<<1],tree[num<<1|1]);
}
//希儿
void xe(int l,int r,int num) //将某点清零 
{
    if(qyn[num])
	{
        int mid=(l+r)>>1;
        tree[num<<1].maxx+=qyn[num];
        tree[num<<1|1].maxx+=qyn[num];
        qyn[num<<1]+=qyn[num];
        qyn[num<<1|1]+=qyn[num];
        qyn[num]=0;
    }
}
//姬子
void jz(int l,int r,int L,int val,int num) 
//将这个飞鱼丸标记qwq 
{
    if(l==r)
	{
        tree[num].maxx=val-tree[num].maxx;
        return;
    }
    int mid=(l+r)>>1;
    xe(l,r,num);
    if(mid<L) jz(mid+1,r,L,val,num<<1|1);
    else jz(l,mid,L,val,num<<1);
    tree[num]=max(tree[num<<1],tree[num<<1|1]);
}
node ask(int l,int r,int L,int R,int num) //标准查询 
{
    if(l==L&&r==R) return tree[num];
    int mid=(l+r)>>1;
    xe(l,r,num);
    if(mid<L) return ask(mid+1,r,L,R,num<<1|1);
    else if(mid>=R) return ask(l,mid,L,R,num<<1);
    else return max(ask(l,mid,L,mid,num<<1),ask(mid+1,r,mid+1,R,num<<1|1));
}
void change(int l,int r,int L,int R,int val,int num) //标准区间修改 
{
    if(l==L&&r==R)
	{
        tree[num].maxx+=val;
        qyn[num]+=val;
        return;
    }
    int mid=(l+r)>>1;
    xe(l,r,num);
    if(mid<L) change(mid+1,r,L,R,val,num<<1|1);
    else if(mid>=R) change(l,mid,L,R,val,num<<1);
    else change(l,mid,L,mid,val,num<<1),change(mid+1,r,mid+1,R,val,num<<1|1);
    tree[num]=max(tree[num<<1],tree[num<<1|1]);
} 
void add(int x,int val) { for(;x<=n;x+=x&-x) blny[x]+=val;} 
//标准区间加 
int sum(int x) //标准区间求和 
{
    int ans=0;
    for(;x;x-=x&-x) ans+=blny[x];
    return ans;
}
int main()
{
    cin >> n >> m;
    build(1,n,1); //建树 
    while(m--)
	{
        cin >> p;
        if(p==1)
		{
            cin >> x >> v;
            jz(1,n,x,v,1); //标记飞鱼丸  
            add(x,x); //嘤嘤嘤能量变
        }
		if(p==2)
		{
            cin >> x >> y;
            int num=sum(y)-sum(x-1);//飞鱼丸 
            if(num)
			{
                node ans=ask(1,n,num,num,1); 
                printf("%d\n",ans.maxx);
                bcy += ans.maxx; //获得能量++ 
                change(1,n,num,num,-ans.maxx,1); 
				//牵一发而动全身 
                add(num,-num);
                continue;
            }
            node ans=ask(1,n,x,y,1);//最大点 
            change(1,n,ans.max_place,ans.max_place,-ans.maxx,1);
            printf("%d\n",ans.maxx);
            bcy += ans.maxx;//同上了qwq 
        }
		if (p == 3) 
		{
            cin >> x >> y >> v; 
            change (1,n,x,y,v,1); //区间修改 
        }
    }
    if(bcy<10000) printf("QAQ");
    else  if(bcy<10000000) printf("Sakura");
    else printf("ice");
    return 0;
}

附36行小模拟这最多也就是个黄题吧
倒序太坑人了CRY

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,num,l,r,val,now,x,a[100005],ans;
bool b[100005];
int main()
{
    cin >> n >> m;
    for ( int i = 1; i <= n; i++ ) cin >> a[i];
    while (m--)
    {
    	cin >> num;
    	if ( num == 1 ) cin >> x >> val , a[x] = val-a[x],b[x] = 1;
		if ( num == 2 )
		{
			cin >> l >> r , val = 0;
			for ( int i = r; i >= l; i-- )
			{
				if (b[i]) { now = i , b[i] = 0 , val = a[i]; break; }
				if (val < a[i]) now = i , val = a[i];
			}
			a[now] = 0 , ans += val;
			cout << val << endl;
		}
		if ( num == 3 )
		{
			cin >> l >> r >> val;
			for ( int i = l; i <= r; i++ ) a[i] += val;
		}
	}
	if (ans<10000) cout<<"QAQ";
	if (ans>=10000&&ans<10000000) cout<<"Sakura";
	if (ans>=10000000) cout<<"ice";
	return 0;
}

实际证明，线段树比模拟共快了400ms！
算了，以后就只打暴力了
谢谢观赏