stl的妙用
关于mutiset的应用的几个题
题意：你可以进行以下操作
- 加入一个数
- 删除一个数
- 输出任意两个数异或最小值
思路：首先我们要知道一个性质(重要!)：两个数差值越小，异或值也越小。
那么我们要求异或最小值，那么答案一定在排序后相邻两个数中产生。
为了便于写，防止在set里面找不到的情况出现，我们手动插入下界和上界。
考虑我们的操作：
对于加入一个数，我们的答案有什么影响呢？
假设我们插入的值是x。
假设我们的情况是：l x r
首先如果l和r都存在，那么显然此时l和r的异或值不可能成为答案，我们把它删去
然后在答案里面加入x^l和 x^r(前提是l，r存在)
1
2
3
4
5
6
7
8
9
10
11
12
13
| void add(ll x)
{
s.insert(x);
multiset<ll>::iterator it1 = s.find(x), it2 = s.find(x);
it1--, it2++;
if(*it1 != -1 && *it2 != up)
res.erase(res.find((*it1) ^ (*it2)));
if(*it1 != -1)
res.insert(x ^ (*it1));
if(*it2 != up)
res.insert(x ^ (*it2));
}
|
对于删一个数的情况呢？
那就和加一个数的操作反过来就行了。
1
2
3
4
5
6
7
8
9
10
11
12
| void del(ll x)
{
multiset<ll>::iterator it1 = s.find(x), it2 = s.find(x);
it1--, it2++;
if(*it1 != -1 && *it2 != up)
res.insert((*it1) ^ (*it2));
if(*it1 != -1)
res.erase(res.find((*it1) ^ x));
if(*it2 != up)
res.erase(res.find(x ^ (*it2)));
s.erase(s.find(x));
}
|
下面是AC代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
const ll up = 1ll<<60;
multiset<ll>s,res;
void add(ll x)
{
s.insert(x);
multiset<ll>::iterator it1 = s.find(x), it2 = s.find(x);
it1--, it2++;
if(*it1 != -1 && *it2 != up)
res.erase(res.find((*it1) ^ (*it2)));
if(*it1 != -1)
res.insert(x ^ (*it1));
if(*it2 != up)
res.insert(x ^ (*it2));
}
void del(ll x)
{
multiset<ll>::iterator it1 = s.find(x), it2 = s.find(x);
it1--, it2++;
if(*it1 != -1 && *it2 != up)
res.insert((*it1) ^ (*it2));
if(*it1 != -1)
res.erase(res.find((*it1) ^ x));
if(*it2 != up)
res.erase(res.find(x ^ (*it2)));
s.erase(s.find(x));
}
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int q;
cin>>q;
s.insert(-1),s.insert(up);
while(q--)
{
int op;
cin>>op;
if(op==1)
{
int x;
cin>>x;
add(x);
}
else if(op==2)
{
int x;
cin>>x;
del(x);
}
else
{
cout<<*res.begin()<<"\n";
}
}
return 0;
}
|
题意：
一次运行包含以下操作:
- 对当前数组排序(不降序),然后删除重复的元素
- 如果当前数组大小是1，那么停止运行，输出运行结果
- 对于数组元素加上一个等差数列{n,n−1,n−2,…,1}其中n是当前数组长度
- 返回第一步
给你q个询问，每次给你i x,表示把a[i]赋值为x。然后运行上述求每次的最终运行结果
通过找规律，我们可以发现，最后的答案是数组最大的元素值+排序后数组中两个数差的最大值。
因为，每次操作，排序后的数组，相邻两个数的差值-1，数组中最大值+1，那么答案就是数组最大的元素值+排序后数组中两个数差的最大值。和上一题类似，不过改成了维护两个数差的最大值。
注意：其实改一个数可以想象成把原本的数删了加入一个新的数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int t,n,q,a[N];
multiset<ll>s,res;
const ll up = 1ll<<60;
void add(ll x)
{
s.insert(x);
multiset<ll>::iterator it1 = s.find(x), it2 = s.find(x);
it1--, it2++;
if(*it1 != -1 && *it2 != up)
res.erase(res.find((*it2) - (*it1)));
if(*it1 != -1)
res.insert(x - (*it1));
if(*it2 != up)
res.insert((*it2) - x);
}
void del(ll x)
{
multiset<ll>::iterator it1 = s.find(x), it2 = s.find(x);
it1--, it2++;
if(*it1 != -1 && *it2 != up)
res.insert((*it2) - (*it1));
if(*it1 != -1)
res.erase(res.find(x - (*it1)));
if(*it2 != up)
res.erase(res.find((*it2) - x));
s.erase(s.find(x));
}
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
cin>>t;
while(t--)
{
cin>>n;
res.clear(),s.clear();
s.insert(-1),s.insert(up);
for(int i = 1;i <= n; i++)
cin>>a[i],add(a[i]);
cin>>q;
while(q--)
{
int i,x;
cin>>i>>x;
del(a[i]);
a[i] = x;
add(a[i]);
if(n==1){
cout<<a[n]<<"\n";
continue;
}
cout<<*(--(--s.end()))+*(--res.end())<<" ";
}
cout<<"\n";
}
return 0;
}
|
维护每个窗口的最早空闲时间，然后更新就行。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| #include <bits/stdc++.h>
#define fi first
#define se second
#define all(a) (a).begin(), (a).end()
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, int> PLI;
void solve() {
int n, m;
cin >> n >> m;
vector<LL> a(n), v(m), belong(n), cnt(m), t(m);
for(auto &x : v) cin >> x;
for(auto &x : a) cin >> x;
sort(all(a));
set<PII> st; // cnt, id
set<PLI> done; // time, id
for(int i = 0; i < m; i ++)
st.insert({0, i});
for(int i = 0; i < n; i ++) {
while(done.size() && done.begin()->fi <= a[i]) {
int gid = belong[done.begin()->se];
done.erase(done.begin());
st.erase(st.find({cnt[gid], gid}));
cnt[gid] --;
st.insert({cnt[gid], gid});
}
auto [nn, gid] = *st.begin();
// cout << nn << ' ' << gid << '\n';
st.erase(st.begin());
cnt[gid] ++;
st.insert({cnt[gid], gid});
done.insert({max(a[i], t[gid])+v[gid], i});
belong[i] = gid;
// cout << t[gid] << '\n';
t[gid] = max(t[gid], a[i])+v[gid];
}
cout << (done.rbegin()->fi) << '\n';
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout << fixed;
int Tcase = 1;
// cin >> Tcase;
while(Tcase --)
solve();
return 0;
}
/*
3 1
100
1 10 301
*/
|
