Submission #69838269

---

Source Code Expand

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
const int maxn = 1e6+5;
class SegmentTree
{
public:
    long long a[4 * maxn], add[4 * maxn];
    inline void push_up(int rt) //向上更新
    {
        a[rt] = (a[rt * 2] + a[rt * 2 + 1]);
    }
    void build(int l, int r, int rt) //从l到r建立线段树
    {
        add[rt]=-1;
        if (l == r)
        {
            a[rt]=1;
            return;
        }
        int mid = (l + r) / 2;
        build(l, mid, rt * 2);
        build(mid + 1, r, rt * 2 + 1);
        push_up(rt);
    }
    inline void push_down(int rt, int l,int r) //向下更新
    {
        if (add[rt] != -1)
        {
            add[rt * 2] = add[rt];
            add[rt * 2 + 1] = add[rt];
            int mid=l+r>>1;
            a[rt * 2] = add[rt] ;
            a[rt * 2 + 1] = add[rt] ;
            add[rt] = -1;
        }

    }
    void updata1(int x, int y, int l, int r, int rt) //线段树区间为从l到r，把区间x到y每个数+k
    {
        if (x <= l && y >= r)
        {
            a[rt] =0;
            add[rt]=0;
            return;
        }
        push_down(rt, l,r);
        int mid = (l + r) / 2;
        if (x <= mid)
            updata1(x, y, l, mid, rt * 2);
        if (y > mid)
            updata1(x, y, mid + 1, r, rt * 2 + 1);
        push_up(rt);
    }
    void updata2(int x, long long k, int l, int r, int rt) //线段树区间为从l到r，把区间x到y每个数+k
    {
        if (l==r)
        {
            a[rt] += k;
            return;
        }
        push_down(rt, l,r);
        int mid = (l + r) / 2;
        if (x <= mid)
            updata2(x, k, l, mid, rt * 2);
        else
            updata2(x, k, mid + 1, r, rt * 2 + 1);
        push_up(rt);
    }
    long long query(int x, int y, int l, int r, int rt) //线段树区间为从l到r，询问区间x到y的和
    {
        if (x <= l && y >= r)
            return a[rt];
        push_down(rt, l, r);
        int mid = (l + r) / 2;
        long long ans = 0;
        if (x <= mid)
            ans += query(x, y, l, mid, rt * 2);
        if (y > mid)
            ans += query(x, y, mid + 1, r, rt * 2 + 1);
        return ans;
    }

}st;



int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n,q;
    cin>>n>>q;
    st.build(1,n,1);
    while (q--)
    {
        int x,y;
        cin>>x>>y;
        int now=st.query(1,x,1,n,1);
        cout<<now<<'\n';
        st.updata1(1,x,1,n,1);
        st.updata2(y,now,1,n,1);
    }
}

Submission Info

Compile Error

Main.cpp: In member function ‘void SegmentTree::push_down(int, int, int)’:
Main.cpp:34:22: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   34 |             int mid=l+r>>1;
      |                     ~^~
Main.cpp:34:17: warning: unused variable ‘mid’ [-Wunused-variable]
   34 |             int mid=l+r>>1;
      |                 ^~~

Judge Result