/*
子矩阵的最值
B*B的子矩阵由
B行长度是B的数组构成
1. 求所有长度是B的数组的最值(横向)
例如(1,1) 这个位置存储的是 (1,1) - (1,B)的最值，横向上
2. 对于上述数组，纵向求最值，查表
两次最值，最大值和最小值， 时间复杂度：250*250 * 2
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 255;
int n, b, m, a[N][N];
int q[N], mxc[N][N], mxr[N][N];
int mnc[N][N], mnr[N][N];
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
cin >> n >> b >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) cin >> a[i][j];
int h = 1, t = 0;
// 每一行做单调队列 ， 求最大值
for (int i = 1; i <= n; i++) {
memset(q, 0, sizeof(q));
h = 1, t = 0;
for (int j = 1; j <= n; j++) {
while (h <= t && j - q[h] + 1 > b) h++;
while (h <= t && a[q[t]][i] <= a[j][i]) t--;
q[++t] = j;
if (j >= b)
mxc[i][j] = a[q[h]][i];
}
}
// 每一列的最大值 ， 这样计算出二维的最大值
for (int i = 1; i <= n; i++) {
memset(q, 0, sizeof(q));
h = 1, t = 0;
for (int j = 1; j <= n; j++) {
while (h <= t && j - q[h] + 1 > b) h++;
while (h <= t && mxc[q[t]][i] <= mxc[j][i]) t--;
q[++t] = j;
if (j >= b)
mxr[i][j] = mxc[q[h]][i];
}
}
// 计算二维的最小值
for (int i = 1; i <= n; i++) {
memset(q, 0, sizeof(q));
h = 1, t = 0;
for (int j = 1; j <= n; j++) {
while (h <= t && j - q[h] + 1 > b) h++;
while (h <= t && a[q[t]][i] >= a[j][i]) t--;
q[++t] = j;
if (j >= b)
mnc[i][j] = a[q[h]][i];
}
}
for (int i = 1; i <= n; i++) {
memset(q, 0, sizeof(q));
h = 1, t = 0;
for (int j = 1; j <= n; j++) {
while (h <= t && j - q[h] + 1 > b) h++;
while (h <= t && mnc[q[t]][i] >= mnc[j][i]) t--;
q[++t] = j;
if (j >= b)
mnr[i][j] = mnc[q[h]][i];
}
}
while (m--) {
int r, c;
cin >> r >> c;
cout << mxr[r + b - 1][c + b - 1] - mnr[r + b - 1][c + b - 1] << endl;
}
return 0;
}
// 对于 k = 1 的情况
// 先把所有的数字按照顺序建立链表
// 从小到大依次删除第 i 个点
// 对于 i,l[i]就是左边第一个大于 i 的位置
// r[i] 就是右边第一个大于 i 的位置
// 贡献就是 a[i]*(i-l[i])*(r[i]-i) , i * 区间个数
// k =1 最大值求和，a[i]*(i-l[i])*(r[i]-i)
// k =2 最大值求和，a[i]*( (l[i]-l[l[i]])*(r[i]-i) + (i-l[i])*(r[r[i]] - r[i]) )
// k 大值求和
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+10;
int n, k;
int pre[N], nxt[N];
int a[N], b[N], c[N];
int cas;
int main() {
cin >> cas;
while (cas--) {
cin >> n >> k;
nxt[n + 1] = n + 1;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
a[x] = i;
pre[i] = i - 1, nxt[i] = i + 1;
}
long long ans = 0;
for (int i = 1; i <= n; i++) {
int x = a[i], y = a[i];
for (int j = 0; j <= k; j++) {
b[j] = y; // 左边第几个的值
y = pre[y];
}
y = a[i];
for (int j = 0; j <= k; j++) {
c[j] = y;
y = nxt[y];
}
for (int j = 1; j <= k; j++) {
ans += 1ll * (b[j - 1] - b[j]) * (c[k - j + 1] - c[k - j]) * i;
}
pre[nxt[x]] = pre[x];
nxt[pre[x]] = nxt[x];
}
cout << ans << endl;
}
return 0;
}
// 比自己矮，直接插队
// 第一个比自己高的，贿赂再插队
// 停在比自己第二高的人的后面
// 建立一个链表，
//从低到高依次处理， l[id] 第一个比他高的位置
//l[l[id]] 第一个比他高的位置
//结果 l[l[id]]+1
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n;
struct node {
int h, id;
bool operator<(const node a)const {
return h < a.h;
}
};
node a[N];
int l[N], r[N], ans[N];
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i].h;
a[i].id = i;
l[i] = i - 1;
r[i] = i + 1;
}
sort(a + 1, a + 1 + n);
// 处理身高最低的人
for (int i = 1; i <= n; i++) {
int id = a[i].id;
ans[id] = l[l[id]] + 1;
// 删除 id
r[l[id]] = r[id];
l[r[id]] = l[id];
}
// 输出结果
for (int i = 1; i <= n; i++)
cout << ans[i] << endl;
return 0;
}
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n;
int pre[N], nxt[N], ans[N];
struct node {
int x, id; // 当前位置的值和下标
bool operator < (const node a)const {
return x < a.x;
}
};
node a[N];
int pos[N]; // 确定输入顺序和 在链表里面的位置
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i].x;
a[i].id = i; // 输入顺序
}
// 建立一个 1 - n的双向链表
for (int i = 1; i <= n; i++) {
pre[i] = i - 1;
nxt[i] = i + 1;
}
sort(a + 1, a + 1 + n);
// i = 3 的时候 a[i].id = 5
for (int i = 1; i <= n; i++)
pos[a[i].id] = i;
// 从最后的输入开始处理
for (int i = n; i >= 1; i--) {
int id = pos[i];
int mn = 1e9, mnid = -1;
if (pre[id] != 0) {
if (mn > a[id].x - a[pre[id]].x) {
mn = a[id].x - a[pre[id]].x;
mnid = a[pre[id]].id;
}
}
if (nxt[id] != n + 1) {
if (mn > a[nxt[id]].x - a[id].x ) {
mn = a[nxt[id]].x - a[id].x ;
mnid = a[nxt[id]].id;
}
}
ans[i] = mnid;
pre[nxt[id]] = pre[id];
nxt[pre[id]] = nxt[id];
}
for (int i = 2; i <= n; i++)
cout << ans[i] << " ";
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int n, x;
map<int, int > mp;
set<int> s;
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> x;
//cout << x << " ";
mp[x] = i;
// 去 set 找一个最接近的
if (s.empty()) {
s.insert(x);
continue;
}
else {
auto it = s.lower_bound(x);
if (it == s.end())
cout << mp[*(--it)] << " ";
else if (it == s.begin())
cout << mp[*it] << " ";
else {
// 前面有，后面也有
int right = *it;
int left = *(--it);
if (right - x >= x - left)
cout << mp[left] << " ";
else
cout << mp[right] << " ";
}
}
s.insert(x);
}
return 0;
}
// 双向链表
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
// 编号 1 -n 设 i 就放在 编号 i 上
int pre[N], nxt[N];
int n, q, opt;
// 连接 x 和 y
void connect(int x, int y) {
nxt[x] = y;
pre[y] = x;
}
// 解除连接
void disconnect(int x, int y) {
nxt[x] = 0;
pre[y] = 0;
}
// 打印 x 所在队列的长度和 元素
void print(int x) {
int tot = 0, head=x;
while(pre[head] !=0)
head = pre[head];
// 统计个数
for (int i = head ; i != 0 ; i = nxt[i])
tot++;
cout << tot << endl;
// 从头输出链表
for (int i = head; i != 0 ; i = nxt[i])
cout << i << " ";
}
int main() {
return 0;
}
// 双向链表
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int val[N], pre[N], nxt[N], idx;
int pos[N], head;
// 将 y 增加到 x 的后面
void insert(int x, int y) {
x = pos[x]; // 值替换成位置
++idx;
val[idx] = y;
int t = nxt[x]; // 存储之前 x 的下一个
nxt[idx] = t;
nxt[x] = idx;
pre[idx] = pre[t];
pre[t] = idx;
}
void init() {
// 0 和 1 用了
pre[1] = 0;
nxt[0] = 1;
head = 1;
idx = 1;
pos[1] = 1;
}
void print() {
for (int i = nxt[head] ; i != 0 ; i = nxt[i])
cout << val[i] << " ";
}
int main() {
init();
for (int i = 1; i <= 10; i++) {
insert(1, i + 1);
}
print();
return 0;
}
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int val[N], nxt[N], idx;
int n, head = 1;
int pos[N]; // pos[i] = j 代表 数字 i 存储的下标是 j
// map<int,int > pos;
// 将 y 插入在 x 后面
void insert(int x, int y) {
int it = pos[x];
++idx; // index
val[idx] = y;
nxt[idx] = nxt[it];
nxt[it] = idx;
pos[y] = idx;
}
void insert1(int x) {
++idx;
val[idx] = x;
nxt[idx] = nxt[head];
nxt[head] = idx;
pos[x] = idx;
}
void init() {
head = 1;
idx = 1;
nxt[1] = 0;
}
void print() {
for (int i = nxt[head] ; i != 0; i = nxt[i])
cout << val[i] << " ";
}
int main() {
cin >> n;
init();
insert1(1);
for (int i = 2; i <= n; i++)
insert(1, i);
print();
return 0;
}
ll solve(int k) {
ll ret = 0;
for (int up = 1; up <= n; up++) { // 枚举上边界
for (int i = 1; i <= m; i++) {
b[i] = 0;
c[i] = 1e9 + 7;
}
for (int dn = up ; dn <= n; dn++) { // 枚举下边界
for (int i = 1; i <= m; i++) {
b[i] = max(b[i], a[dn][i]);
c[i] = min(c[i], a[dn][i]);
}
// 二维压成一维去计算
// 一个维度就是 D任务这一题
ret += calcline(k);
}
}
return ret;
}
#include <bits/stdc++.h>
using namespace std;
const int N = 260;
int n, b, k;
int a[N][N];
int mxr[N][N], mxc[N][N];
int mnr[N][N], mnc[N][N];
int q[N], h, t;
int main() {
cin >> n >> b >> k;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
cin >> a[i][j];
// 求最大值数组和最小值数组，写表
// 求最大值
// 每一行单调队列
for (int i = 1; i <= n; i++) {
h = t = 0;
for (int j = 1; j <= n; j++) {
while (h < t && a[i][q[t - 1]] < a[i][j])
t--;
q[t++] = j;
while (h < t && j - q[h] >= b)
h++;
if (j >= b)
mxr[i][j] = a[i][q[h]];
}
}
// 再去列的范畴求最大值 在 mxr 的基础上
for (int j = 1; j <= n; j++) {
h = t = 0;
for (int i = 1 ; i <= n; i++) {
while (h < t && mxr[q[t - 1]][j] < mxr[i][j])
t--;
q[t++] = i;
while (h < t && i - q[h] >= b)
h++;
if (i >= b)
mxc[i][j] = mxr[q[h]][j];
}
}
// 求最小值 mnc
// 输出结果
for (int i = 1; i <= k; i++) {
int x, y;
cin >> x >> y;
cout << mxc[x + b - 1][y + b - 1] - mnc[x + b - 1][y + b - 1] << endl;
}
return 0;
}
// 限制：能力差小于 k 就行
// 组内成员连续：
// 枚举 r , 维护 最大值，最小值，单调队列
// 判断 最大 - 最小 小于 k , ans+= r - l+1; , r固定的，左端点的个数就是区间的个数
// 大于等于 k , l++, 差值小于 k
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, k;
int a[N];
int q1[N], h1, t1; // 最小
int q2[N], h2, t2; // 最大
long long ans;
int main() {
int T ;
cin >> T;
while (T--) {
h1 = t1 = 0; // 初始化
h2 = t2 = 0;
cin >> n >> k;
ans = 0;
for (int i = 1; i <= n; i++)
cin >> a[i];
// 枚举 r
for (int r = 1, l = 1; r <= n; r++) {
// 最小值
while (h1 < t1 && a[q1[t1 - 1]] > a[r] )
t1--;
q1[t1++] = r;
// 最大值
while (h2 < t2 && a[q2[t2 - 1]] < a[r])
t2--;
q2[t2++] = r;
// 根据差值来, 调整左端点
while (a[q2[h2]] - a[q1[h1]] >= k) {
l++;
if (q1[h1] < l)
h1++;
if (q2[h2] < l)
h2++;
}
ans += r - l + 1;
}
cout << ans << endl;
}
return 0;
}
先排序 x[i] ,
一个单调队列记录左边最高的值
vis1[i] =1:左边有高的
一个单调队列记录右边最高的值
vis2[i] =1:右边有高的
vis1[i] &&vis2[i] res++;
// 暴力，枚举 r , l 的范围， r-m - r
// sum[r] - sum[l-1], 前缀和
// 在 r 固定的基础上枚举 l ，
// sum[r] 固定的
// sum[r] - sum[l-1] 最大，sum[l-1] 最小
// 求 sum[l-1] 最小，单调队列
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
int n, m, a[N];
long long sum[N];
int q[N], h, t;
long long res;
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
sum[i] = sum[i - 1] + a[i];
}
// 单调队列求得是最小值
for (int r = 1; r <= n; r++) {
// 有更优秀的值，
while (h < t && sum[q[t - 1]] > sum[r])
t--;
q[t++] = r;
// 区间长度
while (h < t && r - q[h] > m)
h++;
res = max(res, sum[r] - sum[q[h]]);
}
cout << res;
return 0;
}
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, k;
int a[N];
int q[N], h, t;
int main() {
cin >> n >> k;
for (int i = 1; i <= n; i++)
cin >> a[i];
// 单调队列
for (int i = 1; i <= n; i++) {
// 当前 i 入队， 之前年级比他大，能力不行的，淘汰
while (h < t && a[q[t - 1]] > a[i] )
t--;
q[t++] = i; // 当前人入队
// 看是否有年纪超的
if (i - q[h] >= k)
h++;
if (i >= k)
cout << a[q[h]] << " ";
}
return 0;
}
