关于我的二维线段树炸空间这事

Loser_and_Joker @ 2021-07-16 11:22:20

by Loser_and_Joker @ 2021-07-16 11:22:38

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;

void read(int &sum)
{
    sum=0;char last='w',ch=getchar();
    while (ch<'0' || ch>'9') last=ch,ch=getchar();
    while (ch>='0' && ch<='9') sum=sum*10+ch-'0',ch=getchar();
    if (last=='-') sum=-sum;
}
struct tree { int l,r,u,d,c,lazy; }tr[1010*8][1010*8];
int n,m,q;
int a[1010][1010];
void build(int l,int r,int u,int d,int k1,int k2)
{
    if (l>r || u>d) return ;
    tr[k1][k2].l=l,tr[k1][k2].r=r;
    tr[k1][k2].u=u,tr[k1][k2].d=d;
    tr[k1][k2].lazy=0;
    int mid1=(l+r)/2,mid2=(u+d)/2;
    if (l==r && u==d)
        tr[k1][k2].c=a[mid1][mid2];
    else
    {
        build(l,mid1,u,mid2,k1*2,k2*2);
        build(l,mid1,mid2+1,d,k1*2,k2*2+1);
        build(mid1+1,r,u,mid2,k1*2+1,k2*2);
        build(mid1+1,r,mid2+1,d,k1*2+1,k2*2+1);
        tr[k1][k2].c=tr[k1*2][k2*2].c+tr[k1*2][k2*2+1].c+tr[k1*2+1][k2*2].c+tr[k1*2+1][k2*2+1].c;
    }
}
void lazydown(int k1,int k2)
{
    tr[k1*2][k2*2].c+=(tr[k1*2][k2*2].r-tr[k1*2][k2*2].l+1)*(tr[k1*2][k2*2].d-tr[k1*2][k2*2].u+1)*tr[k1][k2].lazy;
    tr[k1*2][k2*2].lazy+=tr[k1][k2].lazy;
    tr[k1*2][k2*2+1].c+=(tr[k1*2][k2*2+1].r-tr[k1*2][k2*2+1].l+1)*(tr[k1*2][k2*2+1].d-tr[k1*2][k2*2+1].u+1)*tr[k1][k2].lazy;
    tr[k1*2][k2*2+1].lazy+=tr[k1][k2].lazy;
    tr[k1*2+1][k2*2].c+=(tr[k1*2+1][k2*2].r-tr[k1*2+1][k2*2].l+1)*(tr[k1*2+1][k2*2].d-tr[k1*2+1][k2*2].u+1)*tr[k1][k2].lazy;
    tr[k1*2+1][k2*2].lazy+=tr[k1][k2].lazy;
    tr[k1*2+1][k2*2+1].c+=(tr[k1*2+1][k2*2+1].r-tr[k1*2+1][k2*2+1].l+1)*(tr[k1*2+1][k2*2+1].d-tr[k1*2+1][k2*2+1].u+1)*tr[k1][k2].lazy;
    tr[k1*2+1][k2*2+1].lazy+=tr[k1][k2].lazy;
    tr[k1][k2].lazy=0;
}
void change(int l,int r,int u,int d,int k1,int k2,int x,int y,int q,int p,int z)
{
//  printf("%d %d %d %d\n",l,r,u,d);
    if (l>r || u>d) return ;
    if (r<x || y<l || d<q || p<u) return ;
    if (x<=l && r<=y && q<=u && d<=p)
    {

        tr[k1][k2].c+=(r-l+1)*(d-u+1)*z;
        tr[k1][k2].lazy+=z;
    }
    else
    {
        int mid1=(l+r)/2,mid2=(u+d)/2;
        if (tr[k1][k2].lazy!=0) lazydown(k1,k2);
        change(l,mid1,u,mid2,k1*2,k2*2,x,y,q,p,z);
        change(l,mid1,mid2+1,d,k1*2,k2*2+1,x,y,q,p,z);
        change(mid1+1,r,u,mid2,k1*2+1,k2*2,x,y,q,p,z);
        change(mid1+1,r,mid2+1,d,k1*2+1,k2*2+1,x,y,q,p,z);
        tr[k1][k2].c=tr[k1*2][k2*2].c+tr[k1*2][k2*2+1].c+tr[k1*2+1][k2*2].c+tr[k1*2+1][k2*2+1].c;
    }
}
int ask(int l,int r,int u,int d,int k1,int k2,int x,int y,int q,int p)
{
    if (l>r || u>d) return 0;
    if (r<x || y<l || d<q || p<u) return 0;
    if (x<=l && r<=y && q<=u && d<=p)
        return tr[k1][k2].c;
    else
    {
        int mid1=(l+r)/2,mid2=(u+d)/2;
        if (tr[k1][k2].lazy!=0) lazydown(k1,k2);
        return ask(l,mid1,u,mid2,k1*2,k2*2,x,y,q,p)+ask(l,mid1,mid2+1,d,k1*2,k2*2+1,x,y,q,p)+ask(mid1+1,r,u,mid2,k1*2+1,k2*2,x,y,q,p)+ask(mid1+1,r,mid2+1,d,k1*2+1,k2*2+1,x,y,q,p);
    }
}
int main()
{
//  freopen("M.in","r",stdin);
//  freopen("M.out","w",stdout);
    read(n),m=n,read(q);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            a[i][j]=0;
    build(1,n,1,m,1,1);
    for (int i=1;i<=q;i++)
    {
        int x,y,q,p,z;
        read(x),read(y),read(q),read(p),z=1;
        change(1,n,1,m,1,1,x,q,y,p,z);
    }
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=m;j++)
            printf("%d ",ask(1,n,1,m,1,1,i,i,j,j));
        printf("\n");
    }
//  fclose(stdin);fclose(stdout);
    return 0;
}

by FxorG @ 2021-07-16 11:26:02

换成树套树不就行了

by Loser_and_Joker @ 2021-07-16 11:27:23

让我看看树套树是什么

by Froranzen @ 2021-07-16 11:28:19

写个二维差分不行吗……非要写毒瘤数据结构恶心自己干啥啊。

by Loser_and_Joker @ 2021-07-16 11:29:07

二维差分我写了，但我又想练一下线段树。。。。

by FunnyCreatress @ 2021-07-16 11:34:20

四分树假的，随随便便卡成 O(n)，不要写

by Prean @ 2021-07-16 11:50:40

别杀鸡用牛刀

by Cloudmata @ 2021-07-16 13:57:40

YBHtree应该可以O(1)过(doge)

by Loser_and_Joker @ 2021-07-16 14:14:18

@OI人在天涯 ?