题目

题目描述

给出一个长度为$n$的整数序列。你的程序需要依次完成如下操作：

$A~a~b~c$：将区间$[a,b]$中的每个数加上$c$
$M~a~b~c$: 对区间$[a,b]$中的每个数$x$，令$x=max(x,c)$

$Q~a$：求序列第$a$个数的值是多少，以及这个值在之前的询问中改变了多少次，你的程序需要输出这两个值

输入格式

第一行输入一个数$n$，表示序列的长度
接下来一行$n$个数，表示最开始的序列
接下来一行输入一个数$m$，表示操作个数
接下来$m$行，每行一个询问，其中操作的形式如试题描述（参考样例）

输出格式

对于每个询问输出两个数，分别为那个数的值，以及那个数被修改了多少次

样例

样例输入

样例输出

1
2
3

5 1
6 1
5 1

样例说明

第一个操作后序列变成了$5,6,3$
第二次操作后序列变成了$5,6,5$

数据范围与提示

对于$30\%$的数据，$n,m \leqslant 10000$
对于另外$30\%$的数据，操作中的值均随机生成的
对于$100\%$的数据，$n,m \leqslant 10^5$
操作过程中所有数字在int范围内

题解

我太菜了，只会分块……
这道题使用分块非常简单，代码超短（比如我的代码就是最短的），内存也很小（我的内存也是最小的），但是贼慢，跑了$3008ms$（居然还是第8名）
首先我们规定一些变量：$x_i$表示数值，$opt_i$表示操作次数，$xadd_i$表示数值的lazy标志，$optadd_i$表示操作次数的lazy标志，二维数组$q_{i,j}$表示第$i$块中，针对$M~a~b~c$操作的lazy标志，保证一维数组$q_i$中的数值单调递增，$l_i$表示一维数组$q_i$的长度
对于$A~a~b~c$操作，如果$a$和$b$在同一块中，那么就直接下传标记，直接暴力修改即可
如果$a$和$b$不在同一个块中，$a$和$b$所在的块中一样下传标记然后暴力修改，中间的直接$xadd_i+=c,optadd_i++$就可以了
对于$M~a~b~c$操作，如果$a$和$b$在同一块中，那么就直接下传标记，直接暴力修改即可
如果$a$和$b$不在同一个块中，$a$和$b$所在的块中一样下传标记然后暴力修改，对于中间的每一段，如果$c-add_i>q_{i,l_i}$（因为如果小于就没有存储的必要了），就执行$q_{i,++l_i}=c-add_i$
值得一提的是，因为谁也不知道$l_i$等于几，所以当$l_i>1000$时，我们就下传一下标记，清空$q_i$数组
对于$Q~a$，就直接下传标记然后输出$x_i$和$opt_i$即可
但是，整个程序的核心——下传标记还没有讲呢！
对，下面，我们就来讲讲这个函数
假设我们需要下传第$k$段的内容，那么，常规操作就是$x_i+=xadd_k,opt_i+=optadd_k$，但是我们还需要下传$q_i$呢！
我们首先找出比$x_i$大的$q_{k,j}$设它的下标为$(k,temp)$（因为数组中的值是单调递增的，所以直接使用upper-bound即可），如果没有这个$temp$，那就直接正常下传就好了，但是如果有，就说明这个数需要更新成$c$，并且操作次数要加上$l_k-temp+1$（因为单调递增，这个$c-add_k$更新了，后面的肯定都要更新）
听起来很难理解，看看代码实现吧！
附上代码：

#include<algorithm>
#include<iostream>
#include<cmath>
using namespace std;
int n,m,d,x[100010],opt[100010],add[330],Add[330],q[330][1010],l[330];
char op;
void change1(int a,int b,int c)
{
    for(int i=a;i<b;i++) x[i]+=c,opt[i]++;
}
void change2(int a,int b,int c)
{
    for(int i=a;i<b;i++) if(x[i]<c) x[i]=c,opt[i]++;
}
void spread(int k)
{
    for(int i=d*k,temp;i<d*k+d;i++){
    	temp=upper_bound(q[k]+1,q[k]+l[k]+1,x[i])-q[k];
    	if(temp<=l[k]) x[i]=q[k][l[k]],opt[i]+=l[k]-temp+1;
    	opt[i]+=Add[k],x[i]+=add[k];
    }
    l[k]=add[k]=Add[k]=0;
} 
int main()
{
    cin>>n,d=sqrt(n);
    for(int i=0;i<n;i++) cin>>x[i];
    for(int i=0;i<d;i++) q[i][0]=-0x7fffffff;
    cin>>m;
    for(int i=1,a,b,c;i<=m;i++){
    	cin>>op>>a,a--;
    	if(op=='A'){
    		cin>>b>>c,b--;
    		if(!c) continue;
    		if(a/d==b/d){spread(a/d),change1(a,b+1,c);continue;}
            spread(a/d),change1(a,(a/d+1)*d,c);
            for(int i=a/d+1;i<b/d;i++) add[i]+=c,Add[i]++;
            spread(b/d),change1((b/d)*d,b+1,c);
        }
        else if(op=='M'){
            cin>>b>>c,b--;
            if(a/d==b/d){spread(a/d),change2(a,b+1,c);continue;}
            spread(a/d),change2(a,(a/d+1)*d,c);
            for(int i=a/d+1;i<b/d;i++){
        		if(c-add[i]>q[i][l[i]]) q[i][++l[i]]=c-add[i];
        		if(l[i]>1000) spread(i);
            }
            spread(b/d),change2((b/d)*d,b+1,c);
        }
        else spread(a/d),cout<<x[a]<<" "<<opt[a]<<endl;
    }
}