2 条题解

  • 0
    @ 2023-4-26 20:38:50

    一眼模板题

    (10mins后):为什么tmd是区间修改啊

    #include <bits/stdc++.h>
    using namespace std;
    
    const int N = 5e5+10;
    
    int cl[N],cr[N];
    int n,m;
    
    int lowbit(int i)
    {
        return i & -i;
    }
    
    void update(int c[],int i,int val)
    {
        while(i<=n)
        {
            c[i]+=val;
            i+=lowbit(i);
        }
    }
    //求[1,i]的元素的和
    int sum(int c[],int i)
    {
        int res = 0;
        while(i>0)
        {
            res+=c[i];
            i-=lowbit(i);
        }
        return res;
    }
    
    int main()
    {
        cin >> n >> m;
        for(int i=1;i<=m;i++)
        {
            int a,b,c;
            cin >> a >> b >> c;
            if(a == 1)
            {
                update(cl,b,1);
                update(cr,c,1);
            }
            else if(a == 2)
                cout << sum(cl,c) - sum(cr,b-1) << endl;
        }
        return 0;
    }
    
    • 0
      @ 2023-4-26 20:21:47
      #include<bits/stdc++.h>
      using namespace std;
      const int Maxn=50010;
      int CL[Maxn],CR[Maxn];
      int n,m,N=Maxn;
      int lowbit(int x){
          return x&(-x);
      }
      int Sum(int C[], int x){
          int res=0;
          for(; x; x-=lowbit(x)){
              res+=C[x];
          }
        return res;
      }
      void Update(int c[], int x ,int d){
          for(; x<=n;x+=lowbit(x)){
              c[x]+=d;
          }
      }
      int main()
      {
          cin>>n>>m;
          int opt,x,y;
          while(m--){
              cin>>opt>>x>>y;
              if(opt==1){
                  Update(CL,x,1);
                  Update(CR,y,1);
              }
              else{
                  cout<<Sum(CL,y)-Sum(CR,x-1)<<endl;
              }
              
          }
      }
      

      很有精神!

      • 1

      「一本通 4.1 例 3」校门外的树

      信息

      ID
      594
      时间
      1000ms
      内存
      512MiB
      难度
      5
      标签
      递交数
      31
      已通过
      15
      上传者