QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#605173 | #9104. Zayin and Forest | jiangzhihui# | TL | 61ms | 31428kb | C++14 | 2.0kb | 2024-10-02 15:56:23 | 2024-10-02 15:56:24 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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...