带修改的莫队（日常普及知识）

前言：莫涛大神创造出的离线询问算法的带修改版。

注意：莫队只支持单点修改

操作方法

普通的不带修改的莫队算法要把每个询问带上两个关键字（所在的块和端点）排序，现在待修改的莫队算法要带上三个关键字排序。
其实实际上是和普通的莫队一样很简单的思想。
原本的莫队是[l,r]向边界推，现在带修改那么就设设三元(l,r,x)

每个询问中需要包含这么几个元素
l：询问的左边——所在块为第一个关键字
r：询问的右边——第二个关键字
x：在处理这个询问之前，有多少个修改操作——第三个关键字
id：此次询问的序号——用于统计答案

修改数组
x：此次修改哪一个节点的值
y：修改为什么值

一般块的大小我都设为sqrt(n)

像往常一样，我们先读入数据
询问和修改需要用两个计数器
之后就是喜闻乐见的排序：

排序条件

int cmp(const node1 &a,const node1 &b)
{
    if (a.l/unit!=b.l/unit) return a.l/unit<b.l/unit;
    else if (a.r/unit!=b.r/unit) return a.r/unit<b.r/unit;
    else return a.x<b.x;
}

主程序——维护答案

void solve()
{
    int l=1,r=0,now=0;
    for (int i=1;i<=m;i++)
    {
        while (r<q[i].r) update(r+1,1),r++;
        while (r>q[i].r) update(r,-1),r--;
        while (l>q[i].l) update(l-1,1),l--;
        while (l<q[i].l) update(l,-1),l++;
        while (now<q[i].x) change(now+1,1,l,r),now++;
        while (now>q[i].x) change(now,-1,l,r),now--;
        ans[q[i].id]=tot;
    }
}

l和r分别是上一次的操作区间左右端点在什么位置，
now是上一个询问的中修改操作进行到第几个
初始值：l=1，r=0，now=0
左右端点的转移还是像朴素莫队一样
我这里写了一个update函数
喜闻乐见还是该加加，该减减，布拉布拉之类的。。。（原谅博主在这里偷懒）

在转移完左右端点之后，
要专门看一下修改操作是否都完成了，
这些都通过一个change操作完成

void change(int bh,int z,int l,int r)
{
    if (ch[bh].x>=l&&ch[bh].x<=r) update(ch[bh].x,-1);   //删除从前的影响 
    swap(c[ch[bh].x],ch[bh].y);    
    if (ch[bh].x>=l&&ch[bh].x<=r) update(ch[bh].x,1);   //添加影响 
}

其实change操作是我认为最重要的

需要特别留意的是第二个语句，我没有直接赋值，而是用了swap
因为我们在处理之后的询问，有可能需要还原这个修改操作，
所以我们需要时刻记录修改的值，不能直接无脑的覆盖

这里有一道例题：
例题链接
题解链接