https://wangwl.net/static/projects/visualRegex
购物2(二分)
题目描述:
计算鸭去超市购物。他发现,超市出口有n个收银员,一些收银员的工作效率较高,所以在此收银台的结算速度就会更快,经过长时间的观察,第 \(i\) 个收银员,结算一人的商品需要 \(t_i\) 秒。
现在,有 \(m\) 个人需要结算。你的任务是找到完成所有人结算所需要花费的最短时间。
注意:收银台是同时工作的。
输入格式:
输入的第一行给出两个数字 \(n,m\) ——表示收银员的数量和待结账人员的数量。
接下来n行,每行一个数字 \(t_i\) ——表示第i个人结算一人需要的时间。
子任务一: \(1∼5\):
\(1≤n≤10^5\)
\(1≤m≤3×10^5\)
\(1≤t_i≤10^9\)
子任务二: \(6∼8\)
\(1≤n≤10^5\)
\(1≤m≤10^9\)
\(1≤t_i ≤10^9\)
输出格式:
输出一个整数——表示完成所有人结算所需要花费的最短时间。
输入样例1:
2 6
7
10
输出样例1:
28
输入样例2:
7 10
3
8
3
6
9
2
4
输出样例2:
8
说明:
有两个收银员,结算一人所花费的时间分别为 \(7\) 秒和 \(10\) 秒。
在等待的六个人中,前两个人立即占据了这两个收银台。在第 \(7\) 秒,第一张收银台变成空闲,第三个人占据了它。在第 \(10\) 秒,第四个人占据了第二个收银台。在第 \(14\) 秒,第五个人占据了第一个收银台。在第 \(20\) 秒,第二张收银台再次变成空闲,但第六个人决定再等一秒钟(至第 \(21\) 秒),让第一张收银台空出来,然后占据它。这样一来,结账 \(m\) 人只要花费 \(28\)秒就能完成了。
二分
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#define int long long
int n, m, t;
int a[100010];
int read() {
int x;
scanf("%lld", &x);
return x;
}
int check(int x) {
int ans = 0, t = m, s = n;
for(int i = 1; i <= n; i ++) {
s = x / a[i];
ans += s;
t -= s;
if(t <= 0) return 1;
} return 0;
}
void solve() {
n = read(), m = read();
for(int i = 1; i <= n; i ++) {
a[i] = read();
}
int ans = 0;
int l = 0, r = 1e18, mid;
while(l < r) {
mid = l + r >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}
printf("%lld", l);
}
signed main() {
solve();
return 0;
}
区区区间2(线段树)
题目描述:
\(Keven\)现在又遇到了一道区区区间的题目,他觉得这个题目不是很难,于是想考一考你。
题目大意如下:
已知有一个长度为 \(N\) 的初始值为 \(0\) 的序列,对这个序列执行 \(K\) 次操作,
每次操作先给出一个数字 \(op\),
如果 \(op\) 为 \(0\),那么后面将给出两个数字 \(L,R\),表示求区间 \(L-R\) 的和并输出在一行。
如果 \(op\) 为 \(1\),那么后面将给出三个数字 \(L,R,val\),表示将区间 \(L-R\) 的所有数字都与 $val 进行或操作。
输入格式:
第一行两个数字\(N,K(N<200000,K<100000)\),表示序列长度(序列下标从\(1\)开始)和操作次数。
下一行有\(N\)个数字\(a_1,a_2,……,a_n\)(\(a_n\)小于\(1000000\)),表示序列的初始值。
之后\(K\)行,如果\(op\)为\(0\),后面有两个数字\(L,R\)。(\(L<=N,R<=N\))
如果\(op\)为\(1\),后面有三个数字\(L,R,val\)。(\(L<=N,R<=N,val<1e^8\))
输出格式:
如果\(op\)为\(0\),在一行中输出区间\(L-R\)的和。
输入样例:
5 3
1 2 3 4 5
0 1 4
1 2 5 10
0 1 4
输出样例:
10
36
说明
在第一个 \(op=0\) 操作时数组 \(a\) 为 \([1, 2, 3, 4, 5]\),因此 \([1,4]\) 和为$10
在第二个 \(op=0\) 操作时数组\(a\)为\([1, 10, 11, 14, 15]\),因此\([1,4]\)和为\(36\)
线段树
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr)
#define int long long
using namespace std;
const int N = 2e5 + 10;
int n, m, a[N];
struct node {
int l, r;
int s, add;
int a[64];
}tr[N << 2];
void pushup(int u) {
for(int i = 0; i < 64; i ++)
tr[u].a[i] = tr[u << 1].a[i] + tr[u << 1 | 1].a[i];
tr[u].s = tr[u << 1].s + tr[u << 1 | 1].s;
}
void pushdown(int u) {
int add = tr[u].add;
for(int i = 0; i < 64; i ++) {
if(add >> i & 1) {
int x = tr[u << 1].r - tr[u << 1].l + 1;
int y = tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1;
tr[u << 1].s += (x - tr[u << 1].a[i]) * (1ll << i);
tr[u << 1 | 1].s += (y - tr[u << 1 | 1].a[i]) * (1ll << i);
tr[u << 1].a[i] = x;
tr[u << 1 | 1].a[i] = y;
}
}
tr[u << 1].add |= add;
tr[u << 1 | 1].add |= add;
tr[u].add = 0;
}
void build(int u, int l, int r) {
if(l == r) {
tr[u] = {l, r, a[l], 0};
for(int i = 0; i < 64; i ++)
tr[u].a[i] = a[l] >> i & 1;
} else {
tr[u] = {l, r};
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}
void modify(int u, int l, int r, int k) {
if(l <= tr[u].l&&r >= tr[u].r) {
tr[u].add |= k;
int x = tr[u].r - tr[u].l + 1;
for(int i = 0; i <64; i ++) {
if(k >> i & 1) {
tr[u].s += (x - tr[u].a[i]) * (1ll << i);
tr[u].a[i] = x;
}
}
} else {
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(l <= mid) modify(u << 1, l, r, k);
if(r > mid) modify(u << 1 | 1, l, r, k);
pushup(u);
}
}
int query(int u, int l, int r) {
if(l <= tr[u].l&&r >= tr[u].r) {
return tr[u].s;
} else {
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
int ans = 0;
if(l <= mid) ans += query(u << 1, l, r);
if(r > mid) ans += query(u << 1 | 1, l, r);
return ans;
}
}
void solve() {
cin >> n >> m;
for(int i = 1; i <= n; i ++) {
cin >> a[i];
} build(1, 1, n);
while(m --) {
int f, l, r;
cin >> f >> l >> r;
if(f == 0) {
cout << query(1, l, r) << '\n';
} else {
int x;
cin >> x;
modify(1, l, r, x);
}
}
}
signed main()
{
IOS;
int _ = 1;
// cin >> _;
while(_ --)
solve();
return _ ^ _;
}
非严格次大值
题目描述:
相信大家都见过这样的题目:给一个长度为 \(n\) 的数据,有 \(m\) 次询问,每次询问有两个整数 \(l\),\(r\),输出区间 \([l, r]\) 的最大值,这样的题目相信大家都做腻了,
所以现在升级一下,其他条件不变,输出区间 \([l, r]\) 次大值,例如 \([1, 2, 3, 4, 5]\),最大值是 \(5\),次大值是 \(4\)。
注意:为了减少难度,只会有区间查询,不进行区间修改
数据保证每次查询区间最少会有两个数字,并且 \(l\) 和 \(r\) 的范围一定小于数组的长度,如果区间数字为 \([5, 5]\),那么最大值和次大值都为 \(5\).
输入格式:
第一行两个正整数 \(n,m\),表示数组的长度为 \(n\) 以及查询的次数 \(m\)。
第二行有 \(n\) 个整数,两个整数之间空格隔开,表示数组的值。
下面 \(m\) 行,每行两个正整数 \(l,r\),表示要查询的区间。
输出格式:
输出 \(m\) 行,表示每次查询的答案。
数据范围:
\(2 <= n <= 1e5,1 <= m <= 1e5, r - l >= 1,r <= n\),数组中的每个值的范围 \([0,1e9]\)。
输入:
5 3
2 4 1 3 9
1 4
1 5
3 4
输出:
3
4
1
非严格次大值
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0),cout.tie(0)
// #define int long long
#define Mod 998244353
#define inf 0x3f3f3f3f
/*-------Pragmas-------*/
// #pragma GCC optimize(2)
// #pragma GCC optimize(3, "Ofast", "inline")
using namespace std;
const int N = 1e5 + 10;
int a[N], b[N], ans[N], n, m;
struct node {
int l, r, k, id;
};
inline int lowbit(int x) {
return x & -x;
}
vector<node> q;
vector<int> g[N];
struct Tree {
int sum[N];
Tree() {
memset(sum, 0, sizeof sum);
} inline void modify(int x, int y) {
while(x <= n) {
sum[x] += y;
x += lowbit(x);
}
} inline int query(int x) {
int ans = 0;
while(x) {
ans += sum[x];
x -= lowbit(x);
} return ans;
}
}tr;
inline void get(int l, int r, vector<node> h) {
if(l == r) {
for(auto v : h) ans[v.id] = b[l];
return ;
} int mid = l + r >> 1;
for(int i = mid + 1; i <= r; i ++) {
for(auto j : g[i]) {
tr.modify(j, 1);
}
} vector<node> h1, h2;
for(auto v : h) {
int now = tr.query(v.r) - tr.query(v.l - 1);
if(now >= v.k) h2.push_back(v);
else h1.push_back({v.l, v.r, v.k - now, v.id});
} for(int i = mid + 1; i <= r; i ++) {
for(auto j : g[i]) {
tr.modify(j, -1);
}
} get(l, mid, h1);
get(mid + 1, r, h2);
}
inline void solve() {
cin >> n >> m;
for(int i = 1; i <= n; i ++) {
cin >> a[i], b[i] = a[i];
} sort(&b[1], &b[n + 1]);
int k = unique(&b[1], &b[n + 1]) - &b[1];
for(int i = 1; i <= n; i ++) {
a[i] = lower_bound(&b[1], &b[k + 1], a[i]) - b;
g[a[i]].push_back(i);
} for(int i = 1; i <= m; i ++) {
int l, r;
cin >> l >> r;
q.push_back({l, r, 2, i});
} get(1, k, q);
for(int i = 1; i <= m; i ++) {
cout << ans[i] << '\n';
}
}
signed main() {
IOS;
int _ = 1;
// cin >> _;
while(_ --) {
solve();
} return _ ^ _;
}