[Ynoi2006] rmpq

· · 题解

考虑将平面上的区域分成若干个等价类，使得每个等价类进行的修改序列是相同的。

在本题中，每次操作范围为二维正交范围。在一个操作序列下，相当于平面被若干条横竖直线划分成矩形网格，矩形网格中的每个格子为一个等价类。若操作序列长度为 m，则等价类的个数为 O(m^2)。

对操作序列每 B 个分一组进行分治。首先分治处理出左一半操作与右一半操作得到的矩形网格与网格中每个格子的信息，合并两个网格时，只需要将水平、竖直的直线各自归并，就不难将儿子网格的每个格子对应到当前网格的格子中，也就完成了等价类的归并。

由于强制在线，可以每积累到 B 个散操作时就对这些操作分一块，进行分治处理。进行查询操作时，对前面的 \frac{m}{B} 个块的网格中进行点定位来得到信息，并对最后小于 B 个操作暴力查询。

如果使用二进制分组的技巧，即每次在末尾加入大小为 1 的块，并在末尾两块大小相同，且不超过设定阈值 B 时，不断合并末尾两个块。这样同样做到了分治的效果，并且在散块查询时只需要在 O(\log B) 个块中进行点定位，可以在操作复杂度不变的情况下减小常数。

分治处理一个长为 n 的操作序列的操作次数为 T(n) = 2T(\frac{n}{2}) + O(n^2) = O(n^2)。设修改与查询操作次数总和为 n，则操作次数复杂度为 O(\frac{n}{B}\times B^2 + nB)，取 B = \sqrt n 可得最优复杂度为 O(n\sqrt n)。

点定位需要在网格的 x 坐标与 y 坐标中进行二分，时间复杂度为 O(n\sqrt n\log n)，在本题中可以通过。可以使用分散层叠的技巧优化到 O(n\sqrt n)。

#include "lib.h"
#include<bits/stdc++.h>
#define For(i,a,b) for(register int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(register int i=(a);i>=(b);--i)
using namespace std;

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

struct DS{
    int n1,n2;
    vector<int> x1,x2;
    vector<Data> val;
    void init(int N1,int N2){
        n1=N1,n2=N2;
        x1.resize(n1),x2.resize(n2),val.resize(n1*n2);
    }
    int size(){return max(0,n1+n2-2);}
    void init(int x,int dir,Data d1,Data d2){
        if(dir){
            init(1,2);
            x2[0]=x,x1[0]=x2[1]=inf;
        }else{
            init(2,1);
            x1[0]=x,x1[1]=x2[0]=inf;
        }
        val[0]=d1,val[1]=d2;
    }
    Data qval(int x,int y){
        return val[x*n2+y];
    }
    void upd(int x,int y,Data d){
        val[x*n2+y]=d;
    }
    Data ask(int x,int y){
        return qval(upper_bound(x1.begin(),x1.end(),x)-x1.begin(),
                    upper_bound(x2.begin(),x2.end(),y)-x2.begin());
    }
}t[512];
int top;

pii p[261],q[261];
DS merge(DS a,DS b)
{
    DS c;
    c.init(a.n1+b.n1-1,a.n2+b.n2-1);
    int j=0,now=0;
    For(i,0,a.n1-1){
        while(j<b.n1&&b.x1[j]<a.x1[i]){
            p[now]=mkp(i,j);
            c.x1[now]=b.x1[j];
            ++j,++now;
        }
        p[now]=mkp(i,j);
        c.x1[now]=a.x1[i];
        ++now; 
    }
    j=0,now=0;
    For(i,0,a.n2-1){
        while(j<b.n2&&b.x2[j]<a.x2[i]){
            q[now]=mkp(i,j);
            c.x2[now]=b.x2[j];
            ++j,++now;
        }
        q[now]=mkp(i,j);
        c.x2[now]=a.x2[i];
        ++now;
    }
    For(i,0,c.n1-1)
        For(j,0,c.n2-1)
            c.upd(i,j,a.qval(p[i].fi,q[j].fi)*b.qval(p[i].se,q[j].se));
    return c;
}

void update(int x,int dir,Data d1,Data d2){
    t[++top].init(x,dir,d1,d2);
    while(top>1 && t[top].size()<256 && t[top-1].size()<=t[top].size()){
        t[top-1]=merge(t[top-1],t[top]);
        --top;
    }
}

Data query(int x,int y){
    Data ret; ret.clr();
    For(i,1,top) ret*=t[i].ask(x,y);
    return ret;
}