头像

whsstory


访客:22244

离线:7小时前


活动打卡代码 AcWing 362. 区间

whsstory
7小时前
/**********/
#define MAXN 50011
struct Segment_Tree
{
    ll t[MAXN<<2|1];
    #define rt t[num]
    #define tl t[num<<1]
    #define tr t[num<<1|1]
    ll Qsum(un ql,un qr,un l=1,un r=MAXN-1,un num=1)
    {
        if(ql<=l&&r<=qr)return rt;
        un mid=(l+r)>>1;ll ans=0;
        if(ql<=mid)ans+=Qsum(ql,qr,l,mid,num<<1);
        if(qr>mid)ans+=Qsum(ql,qr,mid+1,r,num<<1|1);
        return ans;
    }
    void modify(un pos,ll k,un l=1,un r=MAXN-1,un num=1)
    {
        if(l==r){rt+=k;return;}
        un mid=(l+r)>>1;
        if(pos<=mid)modify(pos,k,l,mid,num<<1);
        else modify(pos,k,mid+1,r,num<<1|1);
        rt=tl+tr;
    }
    ll Qkth(ll k,un l=1,un r=MAXN-1,un num=1)//Query k-th 0
    {
        if(l==r)return l;
        un mid=(l+r)>>1;
        ll fl=mid-l+1-tl;
        if(k<=fl)return Qkth(k,l,mid,num<<1);
        else return Qkth(k-fl,mid+1,r,num<<1|1);
    }
}sgt;
struct Seg
{
    ll l,r,c;
    bool operator <(const Seg& t)const{return r<t.r;}
}a[MAXN];
int main()
{
    ll n=read(),ans=0;
    for(ll i=1;i<=n;++i)a[i].l=read()+1,a[i].r=read()+1,a[i].c=read();
    std::sort(a+1,a+n+1);
    for(ll i=1;i<=n;++i)
    {
        ll k=a[i].c-sgt.Qsum(a[i].l,a[i].r);
        if(k<0)continue;
        ans+=k;
        while(k--)
        {
            ll pos=sgt.Qkth(a[i].r-sgt.Qsum(1,a[i].r));
            sgt.modify(pos,1);
        }
    }
    printf("%lld",ans);
    return 0;
}



whsstory
7小时前

考虑所有$c=1$时,就是个经典的贪心:按右端点排序, 如果当前考虑的线段之内有点则跳过,否则选择最右边的点.
对于一般情况,设$c_i-$线段中已有的点数量 为$k$.
若$k<0$则跳过,否则选择最靠右的$k$个未被选择的点.
直接做时间复杂度为$\mathcal O(nV),V$为值域.
考虑数据结构优化.对于位置$pos$,有点记为1,无点记为0.因此”线段中已有的点数量”等价于一个区间和问题.
考虑”选择最靠右的$k$个未被选择的点.”.寻找某个常数的第$x$个位置是线段树/平衡树 上二分的经典问题.因此每次找当前区间右端点最左侧的0,并暴力单点修改即可,时间复杂度是$\mathcal O(n\log n+V\log V)$
//告别时间复杂度玄学的判负环,从我做起

/**********/
#define MAXN 50011
struct Segment_Tree
{
    ll t[MAXN<<2|1];
    #define rt t[num]
    #define tl t[num<<1]
    #define tr t[num<<1|1]
    ll Qsum(un ql,un qr,un l=1,un r=MAXN-1,un num=1)
    {
        if(ql<=l&&r<=qr)return rt;
        un mid=(l+r)>>1;ll ans=0;
        if(ql<=mid)ans+=Qsum(ql,qr,l,mid,num<<1);
        if(qr>mid)ans+=Qsum(ql,qr,mid+1,r,num<<1|1);
        return ans;
    }
    void modify(un pos,ll k,un l=1,un r=MAXN-1,un num=1)
    {
        if(l==r){rt+=k;return;}
        un mid=(l+r)>>1;
        if(pos<=mid)modify(pos,k,l,mid,num<<1);
        else modify(pos,k,mid+1,r,num<<1|1);
        rt=tl+tr;
    }
    ll Qkth(ll k,un l=1,un r=MAXN-1,un num=1)//Query k-th 0
    {
        if(l==r)return l;
        un mid=(l+r)>>1;
        ll fl=mid-l+1-tl;
        if(k<=fl)return Qkth(k,l,mid,num<<1);
        else return Qkth(k-fl,mid+1,r,num<<1|1);
    }
}sgt;
struct Seg
{
    ll l,r,c;
    bool operator <(const Seg& t)const{return r<t.r;}
}a[MAXN];
int main()
{
    ll n=read(),ans=0;
    for(ll i=1;i<=n;++i)a[i].l=read()+1,a[i].r=read()+1,a[i].c=read();
    std::sort(a+1,a+n+1);
    for(ll i=1;i<=n;++i)
    {
        ll k=a[i].c-sgt.Qsum(a[i].l,a[i].r);
        if(k<0)continue;
        ans+=k;
        while(k--)
        {
            ll pos=sgt.Qkth(a[i].r-sgt.Qsum(1,a[i].r));
            sgt.modify(pos,1);
        }
    }
    printf("%lld",ans);
    return 0;
}



活动打卡代码 AcWing 361. 观光奶牛

whsstory
8小时前
//Wan Hong 3.1
//home
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
typedef long long ll;
typedef unsigned un;
typedef std::pair<ll,ll> pll;
typedef std::string str;
ll read(){ll f=1,x=0;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return f*x;}
ll max(ll a,ll b){return a>b?a:b;}
ll min(ll a,ll b){return a<b?a:b;}
bool umax(ll& a,ll b){if(b>a)return a=b,1;return 0;}
bool umin(ll& a,ll b){if(b<a)return a=b,1;return 0;}
ll abs(ll x){return x>0?x:-x;}
/**********/
#define MAXN 50011
#define MAXM 2000011
ll n,m;
struct Graph
{
    struct edge
    {
        ll v,nxt;
        double w;
    }e[MAXM];
    ll cnt=0,last[MAXN];
    void adde(ll u,ll v,double w)
    {
        e[++cnt].v=v,e[cnt].w=w;
        e[cnt].nxt=last[u],last[u]=cnt;
    }
    void clear()
    {
        cnt=0;
        for(ll i=1;i<=n;++i)last[i]=0;
    }
}e,te;
ll val[MAXN],q[MAXN<<5|1],len[MAXN];
double dis[MAXN];
bool check(double k)
{
    e.clear();
    for(ll u=1;u<=n;++u)
        for(ll i=te.last[u];i;i=te.e[i].nxt)
            e.adde(u,te.e[i].v, te.e[i].w*k-val[u]);
    ll h=1,t=1;
    for(ll i=1;i<=n;++i)dis[i]=1e15,len[i]=0;
    dis[1]=0,q[t++]=1;
    len[1]=1;
    while(h<t)
    {
        ll u=q[h++];
        for(ll i=e.last[u];i;i=e.e[i].nxt)
        {
            ll v=e.e[i].v;
            if(dis[v]>dis[u]+e.e[i].w)len[v]=len[u]+1, dis[v]=dis[u]+e.e[i].w,q[t++]=v;
            if(len[v]>n)return 1;
        }
    }
    return 0;
}
int main()
{
    n=read(),m=read();
    for(ll i=1;i<=n;++i)val[i]=read();
    for(ll i=1;i<=m;++i)
    {
        ll u=read(),v=read(),w=read();
        te.adde(u,v,w);
    }
    double l=-1e6,r=1e6;
    while(r-l>0.001)
    {
        double mid=(l+r)/2;
        if(check(mid))l=mid;
        else r=mid;
    }
    printf("%.2f",l);
    return 0;
}


活动打卡代码 AcWing 234. 放弃测试

whsstory
23小时前
//Wan Hong 3.1
//home
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
typedef long long ll;
typedef unsigned un;
typedef std::pair<ll,ll> pll;
typedef std::string str;
ll read(){ll f=1,x=0;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return f*x;}
ll max(ll a,ll b){return a>b?a:b;}
ll min(ll a,ll b){return a<b?a:b;}
bool umax(ll& a,ll b){if(b>a)return a=b,1;return 0;}
bool umin(ll& a,ll b){if(b<a)return a=b,1;return 0;}
ll abs(ll x){return x>0?x:-x;}
/**********/
#define MAXN 100011
ll a[MAXN],b[MAXN],n,k;
double p[MAXN];
bool check(double x)
{
    for(ll i=1;i<=n;++i)p[i]=a[i]-x*b[i];
    std::sort(p+1,p+n+1);
    double sum=0;
    for(ll i=n;i>k;--i)sum+=p[i];
    return sum>=0;
}
int main()
{
    while(n=read(),k=read(),n||k)
    {
        for(ll i=1;i<=n;++i)a[i]=read();
        for(ll i=1;i<=n;++i)b[i]=read();
        double l=0,r=1e9;
        while(r-l>1e-5)
        {
            double mid=(l+r)/2;
            if(check(mid))l=mid;
            else r=mid;
        }
        printf("%.0f\n",l*100);
    }
    return 0;
}


活动打卡代码 AcWing 222. 青蛙的约会

whsstory
23小时前
//Wan Hong 3.1
//home
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
typedef long long ll;
typedef unsigned un;
typedef std::pair<ll,ll> pll;
typedef std::string str;
ll read(){ll f=1,x=0;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return f*x;}
ll max(ll a,ll b){return a>b?a:b;}
ll min(ll a,ll b){return a<b?a:b;}
bool umax(ll& a,ll b){if(b>a)return a=b,1;return 0;}
bool umin(ll& a,ll b){if(b<a)return a=b,1;return 0;}
ll abs(ll x){return x>0?x:-x;}
const ll INF=1ll<<58;
/**********/
ll exgcd(ll a,ll b,ll& x,ll& y)
{
    if(!b){x=1,y=0;return a;}
    else
    {
        ll t=exgcd(b,a%b,y,x);
        y-=a/b*x;
        return t;
    }
}
ll upd(ll x,ll p){return (x%p+p)%p;}
ll solve(ll a,ll b,ll mod)
{
    ll x,y;
    ll g=exgcd(a,mod,x,y);
    x=upd(x,mod/g);
    if(b%g)return -1ll;
    return upd(x*b/g,mod/g);
}
int main()
{
    ll sx=read(),sy=read(),m=read(),n=read(),L=read();
    ll a=m-n,b=sy-sx;
    if(a<0)a=-a,b=-b;
    ll ans=solve(a,b,L);
    if(ans==-1)puts("Impossible");
    else printf("%lld",ans);
    return 0;
}


活动打卡代码 AcWing 268. 流星

//Wan Hong 3.1
//home
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
typedef long long ll;
typedef unsigned un;
typedef std::pair<ll,ll> pll;
typedef std::string str;
ll read(){ll f=1,x=0;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return f*x;}
ll max(ll a,ll b){return a>b?a:b;}
ll min(ll a,ll b){return a<b?a:b;}
bool umax(ll& a,ll b){if(b>a)return a=b,1;return 0;}
bool umin(ll& a,ll b){if(b<a)return a=b,1;return 0;}
ll abs(ll x){return x>0?x:-x;}
const ll INF=1ll<<58;
/**********/
#define MAXN 300011
struct one
{
    ll l,r,val;
}stone[MAXN];
std::vector<ll>g[MAXN];
ll need[MAXN],ans[MAXN],a[MAXN],la[MAXN],ra[MAXN];
ll n,m;
struct BIT
{
    ll t[MAXN];
    #define lowb (i&-i)
    void modify(ll i,ll k)
    {
        while(i<=m)
        {
            t[i]+=k;
            i+=lowb;
        }
    }
    ll Qsum(ll i)
    {
        ll res=0;
        while(i)
        {
            res+=t[i];
            i-=lowb;
        }
        return res;
    }
}t;

void solve(ll l,ll r,ll begin,ll end)
{
    if(begin>end)return;
    if(l==r)
    {
        for(ll i=begin;i<=end;++i)
            ans[a[i]]=l;
        return;
    }
    ll mid=(l+r)>>1;
    for(ll i=l;i<=mid;++i)
    {
        ll val=stone[i].val;
        if(stone[i].l<=stone[i].r)t.modify(stone[i].l,val),t.modify(stone[i].r+1,-val);
        else t.modify(stone[i].l,val),t.modify(1,val),t.modify(stone[i].r+1,-val);
    }
    ll itl=0,itr=0;
    for(ll i=begin;i<=end;++i)
    {
        ll cnt=0;
        for(std::vector<ll>::iterator it=g[a[i]].begin();it!=g[a[i]].end();++it)
        {
            cnt+=t.Qsum(*it);
            if(cnt>=need[a[i]])break;
        }   
        if(cnt<need[a[i]])need[a[i]]-=cnt,ra[++itr]=a[i];
        else la[++itl]=a[i];
    }
    for(ll i=l;i<=mid;++i)
    {
        ll val=stone[i].val;
        if(stone[i].l<=stone[i].r)t.modify(stone[i].l,-val),t.modify(stone[i].r+1,val);
        else t.modify(stone[i].l,-val),t.modify(1,-val),t.modify(stone[i].r+1,val);
    }
    for(ll i=1;i<=itl;++i)a[begin+i-1]=la[i];
    for(ll i=1;i<=itr;++i)a[begin+itl+i-1]=ra[i];
    solve(l,mid,begin,begin+itl-1),solve(mid+1,r,begin+itl,end);
}
int main()
{
    //freopen("data.in","r",stdin);
    n=read(),m=read();
    for(ll i=1;i<=m;++i)g[read()].push_back(i);
    for(ll i=1;i<=n;++i)need[i]=read(),a[i]=i;
    ll k=read();
    for(ll i=1;i<=k;++i)stone[i].l=read(),stone[i].r=read(),stone[i].val=read();
    stone[k+1].l=1,stone[k+1].r=m,stone[k+1].val=INF;
    solve(1,k+1,1,n);
    for(ll i=1;i<=n;++i)
        if(ans[i]>k)puts("NIE");
        else printf("%lld\n",ans[i]); 
    return 0;
}



整体二分经典题.考虑单个询问如何二分:二分天数$mid$,前$mid$天区间加,最后询问单点.差分/树状数组 维护即可.

然后套上整体二分的板子就好了.(PS:整体二分中用差分时间复杂度就不对了,会退化到平方级别)
时间复杂度$\mathcal O(n\log n\log k)$

代码直接贴了之前在LOJ写的.

/**********/
#define MAXN 300011
struct one
{
    ll l,r,val;
}stone[MAXN];
std::vector<ll>g[MAXN];
ll need[MAXN],ans[MAXN],a[MAXN],la[MAXN],ra[MAXN];
ll n,m;
struct BIT
{
    ll t[MAXN];
    #define lowb (i&-i)
    void modify(ll i,ll k)
    {
        while(i<=m)
        {
            t[i]+=k;
            i+=lowb;
        }
    }
    ll Qsum(ll i)
    {
        ll res=0;
        while(i)
        {
            res+=t[i];
            i-=lowb;
        }
        return res;
    }
}t;

void solve(ll l,ll r,ll begin,ll end)
{
    if(begin>end)return;
    if(l==r)
    {
        for(ll i=begin;i<=end;++i)
            ans[a[i]]=l;
        return;
    }
    ll mid=(l+r)>>1;
    for(ll i=l;i<=mid;++i)
    {
        ll val=stone[i].val;
        if(stone[i].l<=stone[i].r)t.modify(stone[i].l,val),t.modify(stone[i].r+1,-val);
        else t.modify(stone[i].l,val),t.modify(1,val),t.modify(stone[i].r+1,-val);
    }
    ll itl=0,itr=0;
    for(ll i=begin;i<=end;++i)
    {
        ll cnt=0;
        for(std::vector<ll>::iterator it=g[a[i]].begin();it!=g[a[i]].end();++it)
        {
            cnt+=t.Qsum(*it);
            if(cnt>=need[a[i]])break;
        }   
        if(cnt<need[a[i]])need[a[i]]-=cnt,ra[++itr]=a[i];
        else la[++itl]=a[i];
    }
    for(ll i=l;i<=mid;++i)
    {
        ll val=stone[i].val;
        if(stone[i].l<=stone[i].r)t.modify(stone[i].l,-val),t.modify(stone[i].r+1,val);
        else t.modify(stone[i].l,-val),t.modify(1,-val),t.modify(stone[i].r+1,val);
    }
    for(ll i=1;i<=itl;++i)a[begin+i-1]=la[i];
    for(ll i=1;i<=itr;++i)a[begin+itl+i-1]=ra[i];
    solve(l,mid,begin,begin+itl-1),solve(mid+1,r,begin+itl,end);
}
int main()
{
    //freopen("data.in","r",stdin);
    n=read(),m=read();
    for(ll i=1;i<=m;++i)g[read()].push_back(i);
    for(ll i=1;i<=n;++i)need[i]=read(),a[i]=i;
    ll k=read();
    for(ll i=1;i<=k;++i)stone[i].l=read(),stone[i].r=read(),stone[i].val=read();
    stone[k+1].l=1,stone[k+1].r=m,stone[k+1].val=INF;
    solve(1,k+1,1,n);
    for(ll i=1;i<=n;++i)
        if(ans[i]>k)puts("NIE");
        else printf("%lld\n",ans[i]); 
    return 0;
}


活动打卡代码 AcWing 268. 流星

//Wan Hong 3.1
//home
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
typedef long long ll;
typedef unsigned un;
typedef std::pair<ll,ll> pll;
typedef std::string str;
ll read(){ll f=1,x=0;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return f*x;}
ll max(ll a,ll b){return a>b?a:b;}
ll min(ll a,ll b){return a<b?a:b;}
bool umax(ll& a,ll b){if(b>a)return a=b,1;return 0;}
bool umin(ll& a,ll b){if(b<a)return a=b,1;return 0;}
ll abs(ll x){return x>0?x:-x;}
const ll INF=1ll<<58;
/**********/
#define MAXN 300011
struct one
{
    ll l,r,val;
}stone[MAXN];
std::vector<ll>g[MAXN];
ll need[MAXN],ans[MAXN],a[MAXN],la[MAXN],ra[MAXN];
ll n,m;
struct BIT
{
    ll t[MAXN];
    #define lowb (i&-i)
    void modify(ll i,ll k)
    {
        while(i<=m)
        {
            t[i]+=k;
            i+=lowb;
        }
    }
    ll Qsum(ll i)
    {
        ll res=0;
        while(i)
        {
            res+=t[i];
            i-=lowb;
        }
        return res;
    }
}t;

void solve(ll l,ll r,ll begin,ll end)
{
    if(begin>end)return;
    if(l==r)
    {
        for(ll i=begin;i<=end;++i)
            ans[a[i]]=l;
        return;
    }
    ll mid=(l+r)>>1;
    for(ll i=l;i<=mid;++i)
    {
        ll val=stone[i].val;
        if(stone[i].l<=stone[i].r)t.modify(stone[i].l,val),t.modify(stone[i].r+1,-val);
        else t.modify(stone[i].l,val),t.modify(1,val),t.modify(stone[i].r+1,-val);
    }
    ll itl=0,itr=0;
    for(ll i=begin;i<=end;++i)
    {
        ll cnt=0;
        for(std::vector<ll>::iterator it=g[a[i]].begin();it!=g[a[i]].end();++it)
        {
            cnt+=t.Qsum(*it);
            if(cnt>=need[a[i]])break;
        }   
        if(cnt<need[a[i]])need[a[i]]-=cnt,ra[++itr]=a[i];
        else la[++itl]=a[i];
    }
    for(ll i=l;i<=mid;++i)
    {
        ll val=stone[i].val;
        if(stone[i].l<=stone[i].r)t.modify(stone[i].l,-val),t.modify(stone[i].r+1,val);
        else t.modify(stone[i].l,-val),t.modify(1,-val),t.modify(stone[i].r+1,val);
    }
    for(ll i=1;i<=itl;++i)a[begin+i-1]=la[i];
    for(ll i=1;i<=itr;++i)a[begin+itl+i-1]=ra[i];
    solve(l,mid,begin,begin+itl-1),solve(mid+1,r,begin+itl,end);
}
int main()
{
    //freopen("data.in","r",stdin);
    n=read(),m=read();
    for(ll i=1;i<=m;++i)g[read()].push_back(i);
    for(ll i=1;i<=n;++i)need[i]=read(),a[i]=i;
    ll k=read();
    for(ll i=1;i<=k;++i)stone[i].l=read(),stone[i].r=read(),stone[i].val=read();
    stone[k+1].l=1,stone[k+1].r=m,stone[k+1].val=INF;
    solve(1,k+1,1,n);
    for(ll i=1;i<=n;++i)
        if(ans[i]>k)puts("NIE");
        else printf("%lld\n",ans[i]); 
    return 0;
}



如果没有修改,那这就是一个经典的二维数点问题,将询问容斥然后扫描线+树状数组即可.
有修改的情况,使用CDQ基于时间分治,变成没有修改的情况.
时间复杂度$\mathcal O((m+Q)\log (m+Q)\log W)$
PS:询问容斥后查询的两个前缀应分配不同的时间戳,为了正确统计贡献为这些时间戳记录一下是第几个操作即可(代码中的num[])

/**********/
#define MAXN 200011
#define MAXW 2000011
struct Query
{
    ll x,y1,y2,k,dex;
    bool operator <(const Query& t)const
    {
        if(x==t.x)return y2<t.y2;
        return x<t.x;
    }
}a[MAXN];
struct BIT
{
    ll t[MAXW];
    #define lowb (i&-i)
    void modify(ll i,ll k)
    {
        while(i<MAXW)t[i]+=k,i+=lowb;
    }
    ll Qsum(ll i)
    {
        ll res=0;
        while(i)res+=t[i],i-=lowb;
        return res;
    }
}t;
ll ans[MAXN],is_query[MAXN],num[MAXN];
void CDQ(un l,un r)
{
    if(l==r)return;
    un mid=(l+r)>>1;
    CDQ(l,mid),CDQ(mid+1,r);
    std::sort(a+l,a+r+1);
    for(ll i=l;i<=r;++i)
        if(!a[i].y2)
        {
            if(a[i].dex<=mid)t.modify(a[i].y1,a[i].k);
        }
        else
        {
            if(a[i].dex>mid)ans[num[a[i].dex]]+=(t.Qsum(a[i].y2)-t.Qsum(a[i].y1))*a[i].k;
        }
    for(ll i=l;i<=r;++i)
        if(!a[i].y2&&a[i].dex<=mid)t.modify(a[i].y1,-a[i].k);
}
int main()
{
    ll s=read(),w=read(),all=0,dex=0,op;
    while((op=read())!=3)
    {
        ++dex;
        if(op==1)
        {
            ll x=read(),y=read(),k=read();
            a[++all]={x,y,0,k,all};
        }
        else
        {
            is_query[dex]=1;
            ll x1=read(),y1=read(),x2=read(),y2=read();
            a[++all]={x1-1,y1-1,y2,-1,all};num[all]=dex;
            a[++all]={x2,y1-1,y2,1,all};num[all]=dex;
        }
    }
    CDQ(1,all);
    for(ll i=1;i<=dex;++i)
        if(is_query[i])printf("%d\n",ans[i]);
    return 0;
}


活动打卡代码 AcWing 267. 莫基亚

//Wan Hong 3.1
//home
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
typedef int ll;
typedef unsigned un;
typedef std::pair<ll,ll> pll;
typedef std::string str;
ll read(){ll f=1,x=0;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return f*x;}
ll max(ll a,ll b){return a>b?a:b;}
ll min(ll a,ll b){return a<b?a:b;}
bool umax(ll& a,ll b){if(b>a)return a=b,1;return 0;}
bool umin(ll& a,ll b){if(b<a)return a=b,1;return 0;}
ll abs(ll x){return x>0?x:-x;}
/**********/
#define MAXN 200011
#define MAXW 2000011
struct Query
{
    ll x,y1,y2,k,dex;
    bool operator <(const Query& t)const
    {
        if(x==t.x)return y2<t.y2;
        return x<t.x;
    }
}a[MAXN];
struct BIT
{
    ll t[MAXW];
    #define lowb (i&-i)
    void modify(ll i,ll k)
    {
        while(i<MAXW)t[i]+=k,i+=lowb;
    }
    ll Qsum(ll i)
    {
        ll res=0;
        while(i)res+=t[i],i-=lowb;
        return res;
    }
}t;
ll ans[MAXN],is_query[MAXN],num[MAXN];
void CDQ(un l,un r)
{
    if(l==r)return;
    un mid=(l+r)>>1;
    CDQ(l,mid),CDQ(mid+1,r);
    std::sort(a+l,a+r+1);
    for(ll i=l;i<=r;++i)
        if(!a[i].y2)
        {
            if(a[i].dex<=mid)t.modify(a[i].y1,a[i].k);
        }
        else
        {
            if(a[i].dex>mid)ans[num[a[i].dex]]+=(t.Qsum(a[i].y2)-t.Qsum(a[i].y1))*a[i].k;
        }
    for(ll i=l;i<=r;++i)
        if(!a[i].y2&&a[i].dex<=mid)t.modify(a[i].y1,-a[i].k);
}
int main()
{
    ll s=read(),w=read(),all=0,dex=0,op;
    while((op=read())!=3)
    {
        ++dex;
        if(op==1)
        {
            ll x=read(),y=read(),k=read();
            a[++all]={x,y,0,k,all};
        }
        else
        {
            is_query[dex]=1;
            ll x1=read(),y1=read(),x2=read(),y2=read();
            a[++all]={x1-1,y1-1,y2,-1,all};num[all]=dex;
            a[++all]={x2,y1-1,y2,1,all};num[all]=dex;
        }
    }
    CDQ(1,all);
    for(ll i=1;i<=dex;++i)
        if(is_query[i])printf("%d\n",ans[i]);
    return 0;
}