Looksery Cup 2015 F - Yura and Developers 单调栈+启发式合并
2024-10-14 15:07:29
第一次知道单调栈搞出来的区间也能启发式合并。。。
你把它想想成一个树的形式, 可以发现确实可以启发式合并。
#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define PII pair<int, int>
#define PLI pair<LL, int>
#define ull unsigned long long
using namespace std; const int N = 3e5 + ;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + ;
const double eps = 1e-; int n, k, tot, a[N], stk[N], L[N], R[N], sum[N];
vector<int> num[]; void add(int &a, int b) {
a += b; if(a >= mod) a -= mod;
}
int cal(int x, int l, int r) {
auto it1 = upper_bound(num[x].begin(), num[x].end(), r);
auto it2 = lower_bound(num[x].begin(), num[x].end(), l);
return it1 - it2;
}
int main() {
scanf("%d%d", &n, &k);
num[].push_back();
for(int i = ; i <= n; i++) {
scanf("%d", &a[i]);
sum[i] = (sum[i-]+a[i]%k)%k;
num[sum[i]].push_back(i);
}
a[] = a[n+] = inf;
stk[++tot] = ;
for(int i = ; i <= n; i++) {
while(tot && a[stk[tot]] < a[i]) tot--;
L[i] = stk[tot];
stk[++tot] = i;
}
tot = ;
stk[++tot] = n+;
for(int i = n; i >= ; i--) {
while(tot && a[stk[tot]] <= a[i]) tot--;
R[i] = stk[tot];
stk[++tot] = i;
}
LL ans = ;
for(int i = ; i <= n; i++) {
if(i - L[i] < R[i] - i) {
for(int j = L[i]; j < i; j++)
ans += cal((sum[j]+a[i])%k, i, R[i]-);
} else {
for(int j = i; j < R[i]; j++) {
ans += cal((sum[j]-(a[i]%k)+k)%k, L[i], i-);
}
}
}
printf("%lld\n", ans - n);
return ;
} /*
*/
最新文章
- Netsuite >; Foreign Currency Revaluation 外币评估
- border边框的宽度/样式/颜色 全部值
- markdown编辑器使用建议
- 随笔3- list array
- Hbase0.98的环境搭建
- 剑指Offer:面试题4——替换空格(java实现)
- Server2003安装SP2补丁提示密钥无效的解决方法
- [反汇编练习] 160个CrackMe之016
- smarty 内置函数if 等判断
- js 检验密码强度
- Docker部署JavaWeb项目实战(转)
- ASP.NET Web API框架揭秘:路由系统的几个核心类型
- KERMIT,XMODEM,YMODEM,ZMODEM传输协议小结(转)
- Yii的HTML助手
- Flask 视图
- mysql 循环、游标
- 重建二叉树(JAVA)
- ros 查找包路径
- 深度分析:Android4.3下MMS发送到附件为音频文件(音频为系统内置音频)的彩信给自己,添加音频-发送彩信-接收彩信-下载音频附件-预览-播放(三,接收彩信<;2,下载彩信>;)
- js中哈希表的几种用法总结