Description
有一个a*b的整数组成的矩阵，现请你从中找出一个n*n的正方形区域，使得该区域所有数中的最大值和最小值
的差最小。
Input
第一行为3个整数，分别表示a,b,n的值第二行至第a+1行每行为b个非负整数，表示矩阵中相应位置上的数。每
行相邻两数之间用一空格分隔。
100%的数据2<=a,b<=1000,n<=a,n<=b,n<=100
Output
仅一个整数，为a*b矩阵中所有“n*n正方形区域中的最大整数和最小整数的差值”的最小值。
Sample Input
5 4 2
1 2 5 6
0 17 16 0
16 17 2 1
2 10 2 1
1 2 2 2
1 2 5 6
0 17 16 0
16 17 2 1
2 10 2 1
1 2 2 2
Sample Output
1
Solution
单调队列裸题，练手+凑数用
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<queue>
#include<map>
#include<vector>
#include<set>
#define il inline
#define re register
using namespace std;
const int N=;
int n,m,a[N][N],k,t[N],p[N][N],head,tail,q[N][N],u[N][N],v[N][N],ans=(<<);
int main(){
scanf("%d%d%d",&n,&m,&k);
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
scanf("%d",&a[i][j]);
}
}
for(int i=;i<=n;i++){
head=;tail=;
for(int j=;j<=m;j++){
while(head<=tail&&j-t[head]>=k) head++;
while(head<=tail&&a[i][j]<=a[i][t[tail]]) tail--;
t[++tail]=j;p[i][j]=a[i][t[head]];
}
head=;tail=;
for(int j=;j<=m;j++){
while(head<=tail&&j-t[head]>=k) head++;
while(head<=tail&&a[i][j]>=a[i][t[tail]]) tail--;
t[++tail]=j;q[i][j]=a[i][t[head]];
}
}
for(int j=;j<=m;j++){
head=;tail=;
for(int i=;i<=n;i++){
while(head<=tail&&i-t[head]>=k) head++;
while(head<=tail&&p[i][j]<=p[t[tail]][j]) tail--;
t[++tail]=i;u[i][j]=p[t[head]][j];
}
head=;tail=;
for(int i=;i<=n;i++){
while(head<=tail&&i-t[head]>=k) head++;
while(head<=tail&&q[i][j]>=q[t[tail]][j]) tail--;
t[++tail]=i;v[i][j]=q[t[head]][j];
}
}
for(int i=k;i<=n;i++){
for(int j=k;j<=m;j++)
ans=min(ans,v[i][j]-u[i][j]);
}
cout<<ans;
return ;
}
Description
现在请求你维护一个数列，要求提供以下两种操作：1、 查询操作。语法：Q L 功能：查询当前数列中末尾L
个数中的最大的数，并输出这个数的值。限制：L不超过当前数列的长度。2、 插入操作。语法：A n 功能：将n加
上t，其中t是最近一次查询操作的答案（如果还未执行过查询操作，则t=0)，并将所得结果对一个固定的常数D取
模，将所得答案插入到数列的末尾。限制：n是非负整数并且在长整范围内。注意：初始时数列是空的，没有一个
数。
Input
第一行两个整数，M和D，其中M表示操作的个数(M <= 200,000)，D如上文中所述，满足D在longint内。接下来
M行，查询操作或者插入操作。
Output
对于每一个询问操作，输出一行。该行只有一个数，即序列中最后L个数的最大数。
Sample Input
5 100
A 96
Q 1
A 97
Q 1
Q 2
A 96
Q 1
A 97
Q 1
Q 2
Sample Output
96
93
96
93
96
Solution
为什么还有这么水的题目？！
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<queue>
#include<map>
#include<vector>
#include<set>
#define il inline
#define re register
using namespace std;
int n,D,s[],ind=,m=;
il int maxx(int l,int r){
int ans=;
for(l+=m-,r+=m+;l^r^;l>>=,r>>=){
if(!(l&)) ans=max(ans,s[l^]);
if(r&) ans=max(ans,s[r^]);
}
return ans;
}
il void change(int p,int v){
for(s[p+=m]=v,p>>=;p;p>>=)
s[p]=max(s[p+p],s[p+p+]);
}
int main(){
scanf("%d%d",&n,&D);
while(m<n+) m<<=;
char str[];
for(int i=,lst=,x;i<=n;i++){
scanf("%s%d",&str,&x);
if(str[]=='A'){
x=(0ll+x+lst)%D;
change(++ind,x);
}
else{
lst=maxx(ind-x+,ind);
printf("%d\n",lst);
}
}
return ;
}