gghack_Nythix @ 2023-01-17 13:08:22
rt,我求助了别人问题还是没解决
#include <bits/stdc++.h>
#define wccc inline
#define lid (id << 1)
#define rid (id << 1 | 1)
#define int long long
//id >> 1 lid id >> 1 | 1 rid
using namespace std;
const int MAX = 1040000;//问题在这里,如果开大就tle,如果小了就RE
struct seg_tr{
int l,r;
int mx,sum;
int lazy,lazy2;
bool used;
}tr[MAX * 4];
int a[MAX];
void pushdown(int id){
if(tr[id].used){
tr[lid].lazy = tr[id].lazy;
tr[rid].lazy = tr[id].lazy;
tr[lid].lazy2 = tr[id].lazy2;
tr[rid].lazy2 = tr[id].lazy2;
tr[lid].mx = tr[id].lazy + tr[id].lazy2;
tr[rid].mx = tr[id].lazy + tr[id].lazy2;
tr[lid].used = tr[rid].used = 1;
}
else
{
tr[lid].lazy2 += tr[id].lazy2;
tr[rid].lazy2 += tr[id].lazy2;
tr[lid].mx += tr[id].lazy2;
tr[rid].mx += tr[id].lazy2;
}
tr[id].lazy = tr[id].lazy2 = tr[id].used = 0;
}
wccc void bulid_tr(int id,int l,int r){
tr[id].l = l;
tr[id].r = r;
tr[id].mx = -1e19;
if(l == r){//放置到最后节点
tr[id].mx = a[l];
return;
}
int mid = (l + r) >> 1;
bulid_tr(lid,l,mid);
bulid_tr(rid,mid + 1,r);//递归搜索
tr[id].mx = max(tr[lid].mx,tr[rid].mx);//max为左右节点的最大值
}
void update(int id,int l,int r,int vl){
if(l <= tr[id].l && tr[id].r <= r){
tr[id].lazy2 += vl;
tr[id].mx += vl;
return ;
}
pushdown(id);
int mid = (tr[id].l + tr[id].r) >> 1;
if(l <= mid)update(lid,l,r,vl);
if(mid + 1 <= r)update(rid,l,r,vl);
tr[id].mx = max(tr[lid].mx,tr[rid].mx);//max为左右节点的最大值
}
void change(int id,int l,int r,int vl){
if(l <= tr[id].l && tr[id].r <= r){
tr[id].lazy2 = 0;
tr[id].mx = vl;
tr[id].lazy = vl;
tr[id].used = 1;//此节点被覆盖
return ;
}
pushdown(id);
int mid = (tr[id].l + tr[id].r) >> 1;
if(l <= mid)change(lid,l,r,vl);
if(mid + 1 <= r)change(rid,l,r,vl);
tr[id].mx = max(tr[lid].mx,tr[rid].mx);//max为左右节点的最大值
}
int query(int id,int l,int r){
pushdown(id);
if(l <= tr[id].l && tr[id].r <= r){
return tr[id].mx;
}
int res = -1e18;
int mid = (tr[id].l + tr[id].r) >> 1;
if(l <= mid)res = max(query(lid,l,r),res);
if(mid + 1 <= r)res = max(query(rid,l,r),res);//递归搜索
return res;
}
signed main()
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++){
cin >> a[i];
}
bulid_tr(1,1,n);
for (int i = 1; i <= m; i++)
{
int op,x,y,z;
cin >> op;
if(op == 1){
cin >> x >> y >> z;
change(1,x,y,z);
}
if(op == 2){
cin >> x >> y >>z;
update(1,x,y,z);
}
if(op == 3){
cin >> x >> y;
cout << query(1,x,y) << endl;
}
}
}
by forgotmyhandle @ 2023-02-23 23:09:05
我试过了,你输入输出被卡了,和1040000没关系。用 printf 和 scanf 就能过了。
by forgotmyhandle @ 2023-02-23 23:09:41
我刚才 tle 90 也是因为输入输出(