社区讨论

too many or too few lines求助

P3368【模板】树状数组 2参与者 3已保存回复 3

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@mi6up1lc
此快照首次捕获于
2025/11/20 11:07
4 个月前
此快照最后确认于
2025/11/20 11:07
4 个月前
查看原帖
想用线段树水板子,结果WA了2/9/10,求助
CPP
#include<bits/stdc++.h>
using namespace std;
int num[100007],s,n,m,k,x,y,c,cc,xx,yy;
struct node_tree{
    int lft,rgt;
    long long s,lazy;
}seg_tree[400007];
void build_tree(int r,int x,int y){
    seg_tree[r].lft=x,seg_tree[r].rgt=y,seg_tree[r].lazy=0;
    if(x==y){
        seg_tree[r].s=num[x];
        return;
    }
    int mid=(x+y)/2;
    build_tree(2*r,x,mid);
    build_tree(2*r+1,mid+1,y);
    seg_tree[r].s=seg_tree[2*r].s+seg_tree[2*r+1].s;
}
void pushdown(int r)
{
    seg_tree[r*2].lazy+=seg_tree[r].lazy;
    seg_tree[r*2+1].lazy+=seg_tree[r].lazy;
    seg_tree[r*2].s+=(seg_tree[r*2].rgt-seg_tree[r*2].lft+1)*seg_tree[r].lazy;
    seg_tree[r*2+1].s+=(seg_tree[r*2+1].rgt-seg_tree[r*2+1].lft+1)*seg_tree[r].lazy;
    seg_tree[r].lazy=0;
}
long long query(int r,int x,int y){
    if(seg_tree[r].lft>y||seg_tree[r].rgt<x) return 0;
    if(seg_tree[r].lft>=x&&seg_tree[r].rgt<=y) return seg_tree[r].s;
    if(seg_tree[r].lazy) pushdown(r);
    return query(r*2,x,y)+query(r*2+1,x,y);
}
void change(int r,int x,int y){
    if(seg_tree[r].lft>y||seg_tree[r].rgt<x) return;
    if(seg_tree[r].lft>=x&&seg_tree[r].rgt<=y){
        seg_tree[r].s+=(seg_tree[r].rgt-seg_tree[r].lft+1)*k;
        seg_tree[r].lazy+=k;
        return; 
    }
    if(seg_tree[r].lazy) pushdown(r);
    change(r*2,x,y);
    change(r*2+1,x,y);
    seg_tree[r].s=seg_tree[2*r].s+seg_tree[2*r+1].s;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&num[i]);
    build_tree(1,1,n);
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&cc);
        {
            if(cc==1)
            {
                scanf("%d%d%d",&xx,&yy,&k);
                change(1,xx,yy);
            }
            else
            {
                scanf("%d",&xx);
                long long fff=query(1,xx,xx);
                printf("%lld\n",fff);
            }
        }
    }
    return 0;
}

回复

3 条回复,欢迎继续交流。

正在加载回复...