题解 P4970 【全村最好的嘤嘤刀】
Konnyaku_ljc · · 题解
线段树（较简略）+模拟（最短但是没注释）
要不是和我老婆有关，我才不做呢（哼
这道题我一年前就发现了，模拟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！
算了，以后就只打暴力了
谢谢观赏