QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#605173#9104. Zayin and Forestjiangzhihui#TL 61ms31428kbC++142.0kb2024-10-02 15:56:232024-10-02 15:56:24

Judging History

你现在查看的是最新测评结果

  • [2024-10-02 15:56:24]
  • 评测
  • 测评结果:TL
  • 用时:61ms
  • 内存:31428kb
  • [2024-10-02 15:56:23]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e7+5;
typedef long long ll;
struct segtree
{
    ll t[maxn],lazy[maxn];//因为是区间修改所以需要lazy
    int lson[maxn],rson[maxn];
    int cnt=1;

    inline void Pushup(int &k){t[k]=t[lson[k]]+t[rson[k]];}
    inline void Pushdown(int k,ll l,ll r){
        if(lazy[k]){
            if(!lson[k])lson[k]=++cnt;
            if(!rson[k])rson[k]=++cnt;
            //动态开点的Pushdown就这两句不一样——如果这个节点的子节点没有开,就把他申请开
            lazy[lson[k]]+=lazy[k];
            lazy[rson[k]]+=lazy[k];
            ll mid=(l+r)>>1;
            
            t[lson[k]]+=(mid-l+1)*lazy[k];
            t[rson[k]]+=(r-mid)*lazy[k];
            lazy[k]=0;
        }
    }
    inline void update(int &k,ll l,ll r,ll L,ll R,int x){
        if(!k)k=++cnt;
        if(L<=l&&R>=r){
            lazy[k]+=x;t[k]+=(r-l+1)*x;
        }else{
            Pushdown(k,l,r);
            ll mid=(l+r)>>1;
            if(L<=mid)update(lson[k],l,mid,L,R,x);
            if(R>mid)update(rson[k],mid+1,r,L,R,x);
            Pushup(k);
        }
    }
    inline ll query(int k,ll l,ll r,ll L,ll R){
        if(!k)return 0;
        if(L<=l&&R>=r)return t[k];
        Pushdown(k,l,r);
        ll mid=(l+r)>>1;
        ll ans=0;
        if(L<=mid)ans+=query(lson[k],l,mid,L,R);
        if(R>mid)ans+=query(rson[k],mid+1,r,L,R);
        return ans;
    }
} seg;
int main(){
    long long n ;
    int m ;
    scanf("%lld%d",&n,&m);
    
    for(int i=1;i<=m;i++){
        int q;
        scanf("%d",&q);
        if(q==1){
            long long x ;
            int v ;
            scanf("%lld%d" , &x , &v) ;
            int temp=1;
            while(x <= n)
            {
                seg.update(temp,1,n,x,x,v);
                x += (x & (-x)) ;
            }
        }else{
            ll L,R;
            scanf("%lld%lld",&L,&R);
            printf("%lld\n",seg.query(1,1,n,L,R));
        }
    }

    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 61ms
memory: 31428kb

input:

1000000000 20000
2 384578735 526547442
1 64211261 592970906
1 512065247 448267721
1 44993150 127180320
1 880319036 927623947
1 170536687 572121854
1 896600029 804033011
1 666246328 754201635
1 654066651 179982083
2 240989825 984888006
2 372004567 858916479
2 76127818 98606736
1 181794163 902842353
1...

output:

0
43148875202
17613404710
0
32808578044
28190043566
15641637055
78276219892
14955165236
20262224725
105057452192
17002492367
57916137452
27165464255
72766353838
39458327919
38294102627
264448717384
0
70928519548
279674530483
88885017175
111664599432
69703816663
211506104092
104120007714
34403738515
...

result:

ok 6649 lines

Test #2:

score: -100
Time Limit Exceeded

input:

1000000000000000000 100000
1 384578735 526547442
1 64211261 592970906
1 512065247 448267721
1 44993150 127180320
1 880319036 927623947
1 170536687 572121854
1 896600029 804033011
2 666246328 931651408754201635
1 654066651 179982083
1 984888006 240989825
1 372004567 858916479
1 76127818 98606736
1 18...

output:

144205553442
497561506762
903930740555
878459229726
689906696633
859703313829
735231510045
1177875391120
1461659121798
1612314483744
2027462020547
1991476058156
2381861014705
2033973986301
2117738140401
2946661001323
2187638958334
2593068002437
1854182975909
2262561461341
3038788266419
3070435321746...

result: