QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#883563 | #7641. Range Sets | DeltaCR | TL | 0ms | 0kb | C++14 | 2.5kb | 2025-02-05 17:01:06 | 2025-02-05 17:01:07 |
Judging History
answer
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 2e5;
const int X = 1e5;
const int Q = 1e5;
int m;
map<int, int> mp;
vector<int> val;
struct Opt
{
char op;
int l, r, x, k;
} opt[Q + 5];
struct BIT
{
private:
int tree[N + 5];
int lowbit(int x)
{
return x & -x;
}
void update(int x, int d)
{
while (x <= m)
{
tree[x] += d;
x += lowbit(x);
}
}
public:
void update(int l, int r, int d)
{
update(l, d);
update(r + 1, -d);
}
int query(int x)
{
int res = 0;
while (x)
{
res += tree[x];
x -= lowbit(x);
}
return res;
}
} ans;
struct Chtholly
{
private:
map<int, bool> ch;
void split(int x) // 将 x 所在段 [l, r] 分为 [l, x - 1] 与 [x, r] 两部分
{
ch[x] = prev(ch.upper_bound(x))->second;
}
public:
void init(int n)
{
ch[1] = ch[n + 1] = 0;
}
void update(int l, int r, bool x) // 将 [l, r] 内的值修改为 x
{
split(l), split(r + 1);
for (auto i = ch.find(l); i != ch.find(r + 1); ++i)
if (i->second != x)
ans.update(mp[i->first], mp[next(i)->first - 1], x - i->second);
for (auto i = next(next(ch.find(l))); i != ch.find(r + 1); ++i)
ch.erase(prev(i));
ch[l] = x;
}
} have[X + 5];
void init()
{
sort(val.begin(), val.end());
val.erase(unique(val.begin(), val.end()), val.end());
for (int i = 0; i < val.size(); ++i) mp[val[i]] = i + 1;
m = val.size();
}
int main()
{
int n, q;
cin >> n >> q;
for (int i = 1; i <= q; ++i)
{
have[i].init(n);
cin >> opt[i].op;
if (opt[i].op == '+' || opt[i].op == '-')
{
cin >> opt[i].l >> opt[i].r >> opt[i].x;
val.push_back(opt[i].l);
val.push_back(opt[i].r);
}
else
{
cin >> opt[i].k;
val.push_back(opt[i].k);
}
}
init();
for (int i = 1; i <= q; ++i)
{
if (opt[i].op == '+') have[opt[i].x].update(opt[i].l, opt[i].r, true);
else if (opt[i].op == '-') have[opt[i].x].update(opt[i].l, opt[i].r, false);
else cout << ans.query(mp[opt[i].k]) << endl;
}
return 0;
}
詳細信息
Test #1:
score: 0
Time Limit Exceeded
input:
736 10 ? 1