树状数组9分求调

protractor @ 2024-02-17 11:25:22

by 大眼仔Happy @ 2024-02-17 11:36:27

@protractor 哥你这样不超时吗

by ikun_newperson @ 2024-02-17 11:37:02

#include<iostream>
#define lowbit(x) (x&(-x))
#define cha(x,y) (qzh(y)-qzh(x-1))
using namespace std;
int sz[500050];
int a[500050];
int n,m,k,l,b;
void gai(int i,int x)
{
    a[i]+=x;
    while(i<=n)
    {
        sz[i]+=x;
        i+=lowbit(i);
    }
}
int qzh(int x)
{
    int ans=0;
    while(x)
    {
        ans+=sz[x];
        x-=lowbit(x);
    }
    return ans;
}
int main()
{
    //freopen("P4513_2.in","r",stdin);
    //freopen("P4513.out","w",stdout); 
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>l;
        gai(i,l);
    }
    //for(int i=1;i<=n;i++)
    //    cout<<sz[i]<<' ';
    //cout<<'\n';
    //for(int i=1;i<=n;i++)
    //    cout<<qzh(i)<<' ';
    //cout<<'\n';
    for(int i=1;i<=m;i++)
    {
        cin>>k>>l>>b;
        if(k-1) gai(l,b-a[i]);
        else
        {
            if(l>b) {int z=l;l=b,b=z;}
            int minn=500000001;
            int maxx=-500000001;
            for(int i=l;i<=b;i++)
            {
                minn=min(qzh(i-1),minn);
                maxx=max(qzh(i)-minn,maxx);
            }
            cout<<maxx<<'\n';
        }
    }
    return 0;
}

by ikun_newperson @ 2024-02-17 11:42:03

• 1. 你超时了，树状数组过不了，得用线段树
• 2. 记得开 4*5*10^{5} ,不然会 re

by protractor @ 2024-02-17 12:10:03

啊啊啊（线段树不会）
谢谢各位dalao，学线段树去了T_T

by protractor @ 2024-02-17 12:11:01

对了WA是怎么回事
@_ikun_newperson @大眼仔Happy