分块70pts求调
查看原帖
分块70pts求调
1408853
Augustus_Deception楼主2025/8/30 11:16

写的分块但是不知道为什么莫名WA了3个点

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+7;
int n,m,blk,bl[N];      
int a[N],sum[N],tag[N];  
void init()
{
    blk=sqrt(n);
    for(int i=1;i<=n;i++)
    {
        bl[i]=(i-1)/blk+1;  
        sum[bl[i]]+=a[i];
    }
}
int query(int l,int r)
{
    int bint=bl[l],blr=bl[r];
    int res=0;
    if(bint==blr)
    {
        for(int i=l;i<=r;i++) res+=a[i]+tag[bint]; 
        return res;
    }
    for(int i=l;i<=bint*blk;i++ ) res+=a[i]+tag[bint];
    for(int i=(blr-1)*blk+1;i<=r;i++) res+=a[i]+tag[blr];
    for(int i=bint+1;i<blr;i++) res+=sum[i];
    return res;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    init(); 
    while(m--)
    {
        int op,x,y,v;
        cin>>op>>x;
        if(op==1)
        {
            cin>>v;
            a[x]+=v;
            sum[bl[x]]+=v;
        }
       		else 
			{
			   	cin>>y;
				cout<<query(x,y)<<'\n';
			}
    }
    return 0;
}
2025/8/30 11:16
加载中...