【Codeforces 1042D】Petya and Array
and Codeforces Array
2023-09-14 09:03:44 时间
【链接】 我是链接,点我呀:)
【题意】
【题解】
把a[i]处理成前缀和 离散化. 枚举i从1..n假设a[i]是区间和的a[r] 显然我们需要找到a[r]-a[l]【代码】
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5;
int n;
ll t;
ll a[N+10];
ll b[N*2+10];
map<ll,int> dic,dic1;
int lowbit(int x){
return x&(-x);
}
ll get_sum(int x){
ll ans = 0;
while (x>0){
ans = ans + b[x];
x = x-lowbit(x);
}
return ans;
}
void add(int x){
while (x<=2*N+2){
b[x]= b[x]+1;
x = x + lowbit(x);
}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin >> n >> t;
dic[0] = 1;
dic[0+t] = 1;
for (int i = 1;i <= n;i++) {
cin >> a[i];
a[i]+=a[i-1];
dic[a[i]] = 1;
dic[a[i]+t] = 1;
}
int cnt = 0;
for (auto temp:dic){
cnt++;
dic1[temp.first] = cnt;
}
add(dic1[0+t]);
//cout<<dic1[0+t]<<endl;
ll fans = 0;
for (int i = 1;i <= n;i++){
ll temp1 = get_sum(cnt)-get_sum(dic1[a[i]]);
fans = fans + temp1;
add(dic1[a[i]+t]);
}
cout<<fans<<endl;
return 0;
}
="">
相关文章
- Golang: Values, Types and Variables
- 【论文阅读】Detecting Spacecraft Anomalies Using LSTMs and Nonparametric Dynamic Thresholding
- MIT_6.s081_Lab3:Xv6 and PageTable
- What's The Difference Between Microbiome and Microbiota?
- CodeForces 750A New Year and Hurry
- A. The Fair Nut and Elevator (Codeforces Round #526 (Div. 2))
- 诡异的R包Hmisc安装错误unable to collate and parse R files for package以及解决方案
- ORA-24940: invalid combination of string namespace, string presentation and string receive protocol ORACLE 报错 故障修复 远程处理
- ORA-31067: XML nodes must be updated with valid nodes and of the same type ORACLE 报错 故障修复 远程处理
- ORA-31670: Username argument must be specified and non-null. ORACLE 报错 故障修复 远程处理
- ORA-39359: Source time zone version is string and target time zone version is string. ORACLE 报错 故障修复 远程处理
- ORA-01295: DB_ID mismatch between dictionary string and logfiles ORACLE 报错 故障修复 远程处理
- ORA-03245: Tablespace has to be dictionary managed, online and permanent to be able to migrate ORACLE 报错 故障修复 远程处理
- ORA-16047: DGID mismatch between destination setting and target database ORACLE 报错 故障修复 远程处理
- JD Edwards and Oracle: Working Together for Perfection(jdeoracle)
- 条件MySQL 子句之间`AND`操作符多条件查询(mysql多个and)
- Exploring the Power of Delphi and Redis for HighPerformance Data Storage and Retrieval.(delphiredis)
- Learn the Art of Linux Catch: Tips and Tricks for Effective System Monitoring(linuxcatch)
- Understanding Redis Wait: The Key to Efficient and Effective Distributed Processing(rediswait)
- Oracle数据库中的AND查询(oracle and查询)
- MySQL中AND的使用方法及含义解析(mysql中and的含义)
- Mysql中强大的AND运算符的使用方法探究(mysql中and的使用)
- MySQL中的AND和OR使用逻辑运算符优化查询语句(mysql中and与or)
- Oracle中使用AND运算符的示例分析(oracle中and用法)