91tps非差分求调WA#2
查看原帖
91tps非差分求调WA#2
783233
1925153zty楼主2024/8/23 17:58
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll read()
{
    ll ans=0;
    ll fh=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-')
        fh=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    ans=(ans<<1)+(ans<<3)+c-'0',c=getchar();
    return ans*fh;
};
const ll N=2e6+9;
struct dd
{
    ll zz,bj1,bj2;
}tr[2*N];
ll n,m;
ll bu(ll x,ll y,ll z)
{
    if(x==y)
    {
        tr[z].zz=read();
        return tr[z].zz;
    }
    ll mid=x+y>>1;
    tr[z].zz=bu(x,mid,z<<1)+bu(mid+1,y,(z<<1)+1);
    return tr[z].zz;
};
void push(ll x,ll l,ll r)
{
    tr[x<<1].bj1+=tr[x].bj1;
    tr[(x<<1)+1].bj1+=tr[x].bj1+(tr[x].bj2)*((l+r>>1)-l+1);
    tr[x<<1].bj2+=tr[x].bj2;
    tr[(x<<1)+1].bj2+=tr[x].bj2;
    ll mid=l+r>>1;
    tr[x<<1].zz+=(mid+1-l)*(2*tr[x].bj1+tr[x].bj2*(mid-l))/2;
    tr[(x<<1)+1].zz+=(r-mid)*(2*(tr[x].bj1+(tr[x].bj2)*(mid-l+1))+tr[x].bj2*(r-mid-1))/2;
    tr[x].bj1=0,tr[x].bj2=0;
};
void cr(ll x,ll y,ll l,ll r,ll z,ll u,ll p)
{
    if(l>y||r<x)
    return;
    if(x>=l&&y<=r)
    {
    	int qz=u+p*(x-l);
        tr[z].bj1+=u+p*(x-l),tr[z].bj2+=p;
        tr[z].zz+=(y+1-x)*(2*qz+p*(y-x))/2;
//        cout<<x<<" "<<y<<" "<<tr[z].bj1<<" "<<tr[z].bj2<<" "<<tr[z].zz<<endl;
        return;
    }
    ll mid=x+y>>1;
    if(tr[z].bj1)
    push(z,x,y);
    if(l<=mid)
    cr(x,mid,l,r,z<<1,u,p);
    if(r>=mid+1)
    cr(mid+1,y,l,r,(z<<1)+1,u,p);
    tr[z].zz=tr[z<<1].zz+tr[(z<<1)+1].zz;
};
ll cx(ll x,ll y,ll l,ll r,ll z)
{
    if(l>y||r<x)
    return 0;
    if(x>=l&&y<=r)
    return tr[z].zz;
    if(tr[z].bj1)
    push(z,x,y);
    ll mid=x+y>>1;
    ll ans=0;
    if(l<=mid)
    ans+=cx(x,mid,l,r,z<<1);
    if(r>=mid+1)
    ans+=cx(mid+1,y,l,r,(z<<1)+1);
    return ans;
}
int main()
{
    n=read(),m=read();
    bu(1,n,1);
    for(ll i=1,a,b,c,k,d;i<=m;i++)
    {
        a=read();
        if(a==1)
        {
            b=read(),c=read(),k=read(),d=read();
            cr(1,n,b,c,1,k,d);
//            for(int i=1;i<=n;i++)
//            cout<<cx(1,n,i,i,1)<<endl;
//            cout<<cx(1,n,1,n,1)<<endl;
        }
        else
        {
            b=read();
            cout<<cx(1,n,b,b,1)<<endl;
        }
    }
}

91

2024/8/23 17:58
加载中...