题解：CF707E Garlands

· · 题解

写人类智慧紫题题解涨涨 rp。

前置知识：二维树状数组。

:::info[模板我放这儿了]

template<typename T=ll>class fenwick{
    vector<vector<T>>t;
    int n,m;
public:
    fenwick(int _n,int _m):n(_n+1),m(_m+1){t.assign(n,vector<T>(m));}
    fenwick(int _n,int _m,T):n(_n+1),m(_m+1){t.assign(n,vector<T>(m));}
#define lowbit(x)(x&-(x))
    void add(int x,int y,T cnt){
        for(int i=x;i<n;i+=lowbit(i))
            for(int j=y;j<m;j+=((j)&-(j)))
                t[i][j]+=cnt;
    }
    T query(int x,int y){
        T ans=0;
        for(int i=x;i>0;i-=lowbit(i))
            for(int j=y;j>0;j-=lowbit(j))
                ans+=t[i][j];
        return ans;
    }
    T query(int lx,int ly,int rx,int ry){
        return query(rx,ry)-query(rx,ly-1)-query(lx-1,ry)+query(lx-1,ly-1);
    }
#undef lowbit
};

:::

看这题，不挺板子的吗？

哎不对，q\le 10^6，会逝。

那不就记一个 flag 表示当前这一串灯泡开没开，在每次 ASK 时更新，时间复杂度 O((\sum_{i=1}^q[op_i=\texttt{ASK}])(\log nm\sum_{i=1}^klen_i)) 挺好的！（吗？）

然后我同学就交了一发，tle on 17。

:::info[他的 code]

#include<bits/stdc++.h>
using namespace std;
const int N = 2510;
long long n,m,c[2510][2510],flag[2010],sz;
string op;
struct dc
{
    long long hh[2010];
    long long ll[2010];
    long long w[2010];
    long long len;
};
dc dcs[2010];
int lowbit(int x)
{
    return x&-x;
}
void add(long long c[][N] , int x,int y,long long v)
{
    for(int i=x;i<=n;i+=lowbit(i))
    {
        for(int j=y;j<=m;j+=lowbit(j))
        {
            c[i][j]+=v;
        }
    }
    return;
} 
long long query(long long c[][N],int x,int y)
{
    long long sum=0;
    for(int i=x;i>=1;i-=lowbit(i))
    {
        for(int j=y;j>=1;j-=lowbit(j))
        {
            sum+=c[i][j];
        }
    }
    return sum;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>sz;
    for(int i=1;i<=sz;i++) flag[i]=1;
    for(int i=1;i<=sz;i++)
    {
        cin>>dcs[i].len;
        for(int j=1;j<=dcs[i].len;j++)
        {
            cin>>dcs[i].hh[j]>>dcs[i].ll[j]>>dcs[i].w[j];
        }
    }
    long long q;
    cin>>q;
    while(q--)
    {
        long long l,r,x,y;
        cin>>op>>l;
        if(op=="ASK") 
        {
            cin>>r>>x>>y;
            for(int i=1;i<=sz;i++)
            {
                if(flag[i]==0) continue;
                for(int j=1;j<=dcs[i].len;j++)
                {
                    int a=dcs[i].hh[j],b=dcs[i].ll[j],k=dcs[i].w[j];
                    add(c,a,b,k);
                }
            }
            cout<<query(c,x,y)-query(c,x,r-1)-query(c,l-1,y)+query(c,l-1,r-1)<<"\n";
            for(int i=1;i<=sz;i++)
            {
                if(flag[i]==0) continue;
                for(int j=1;j<=dcs[i].len;j++)
                {
                    int a=dcs[i].hh[j],b=dcs[i].ll[j],k=dcs[i].w[j];
                    add(c,a,b,-k);
                }
            }
        }
        else flag[l]=1-flag[l];
    }
}

:::

然鹅实际上不用那么肝，再存一个 lst 表示树状数组中记录的开没开，就不用每次删了。

整理一下思路：记录 flag 表示当前这一串灯泡开没开，lst 表示当前树状数组中记录没记录，在每次 ASK 时更新不就好了？！

:::success[AC code]{open}

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
template<typename T=ll>class fenwick{
    vector<vector<T>>t;
    int n,m;
public:
    fenwick(int _n,int _m):n(_n+1),m(_m+1){t.assign(n,vector<T>(m));}
    fenwick(int _n,int _m,T):n(_n+1),m(_m+1){t.assign(n,vector<T>(m));}
#define lowbit(x)(x&-(x))
    void add(int x,int y,T cnt){
        for(int i=x;i<n;i+=lowbit(i))
            for(int j=y;j<m;j+=((j)&-(j)))
                t[i][j]+=cnt;
    }
    T query(int x,int y){
        T ans=0;
        for(int i=x;i>0;i-=lowbit(i))
            for(int j=y;j>0;j-=lowbit(j))
                ans+=t[i][j];
        return ans;
    }
    T query(int lx,int ly,int rx,int ry){
        return query(rx,ry)-query(rx,ly-1)-query(lx-1,ry)+query(lx-1,ly-1);
    }
#undef lowbit
};
template<typename T=ll>class segtree{
    fenwick<T>t0,t1,t2,t3;
    T pre(int x,int y){
        return  x*y*t0.query(x,y)
            -   x*  t1.query(x,y)
            -     y*t2.query(x,y)
            +       t3.query(x,y);
    };
public:
    segtree(int n,int m):t0(n+5,m+5),t1(n+5,m+5),t2(n+5,m+5),t3(n+5,m+5){}
    segtree(int n,int m,T):t0(n+5,m+5),t1(n+5,m+5),t2(n+5,m+5),t3(n+5,m+5){}
    void add(int lx,int ly,int rx,int ry,T cnt){
        t0.add(lx,ly,cnt);t0.add(lx,ry+1,-cnt);t0.add(rx+1,ly,-cnt);t0.add(rx+1,ry+1,cnt);
        t1.add(lx,ly,cnt*ly);t1.add(lx,ry+1,-cnt*(ry+1));t1.add(rx+1,ly,-cnt*ly);t1.add(rx+1,ry+1,cnt*(ry+1));
        t2.add(lx,ly,cnt*lx);t2.add(lx,ry+1,-cnt*lx);t2.add(rx+1,ly,-cnt*(rx+1));t2.add(rx+1,ry+1,cnt*(rx+1));
        t3.add(lx,ly,cnt*lx*ly);t3.add(lx,ry+1,-cnt*lx*(ry+1));t3.add(rx+1,ly,-cnt*(rx+1)*ly);t3.add(rx+1,ry+1,cnt*(rx+1)*(ry+1));
    };
    T query(int lx,int ly,int rx,int ry){
        ++lx,++ly,++rx,++ry;
        return pre(rx,ry)-pre(rx,ly-1)-pre(lx-1,ry)+pre(lx-1,ly-1);
    };
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    int n,m,k;
    cin>>n>>m>>k;
    fenwick tree(n,m,0ll);
    vector<vector<tuple<int,int,int>>>light(k);
    vector<bool>flag(k,1),lst(k);
    for(auto&i:light){
        int siz;
        cin>>siz;
        i.resize(siz);
        for(auto&[x,y,j]:i)cin>>x>>y>>j;
    }
    int q,t;
    cin>>q;
    string op;
    while(q--){
        cin>>op;
        if(op=="ASK")[[unlikely]]{
            for(auto i:views::iota(0,k))
                if(flag[i]!=lst[i]){
                    lst[i]=flag[i];
                    for(auto[x,y,t]:light[i])
                        tree.add(x,y,t*((flag[i]<<1)-1));
                }
            int lx,ly,rx,ry;
            cin>>lx>>ly>>rx>>ry;
            cout<<tree.query(lx,ly,rx,ry)<<"\n";
        }else[[likely]]cin>>t,--t,flag[t]=1-flag[t];
    }
    return 0;
}

AC Submission :::

警示后人：如果你懒用区间加区间求和的代码写会有 16 常大数，哦！