G-鸡格线(map + 内置二分写法)
思路 or 题解:
通过 我们可得到: 经过至多 次
- 0 -> 0
- 1~99 -> 99
- 100 ~ inf ->100
虽然 可能很大,但是 如果 等于 或 或 修改就没有效果了,这也是这个题可以做的隐藏条件!
线段树的写法这里就不再提了,我赛时是写的线段树,赛后发现 map 也可以做 并且 时间和代码量都比线段树更优 QAQ
我们通过 map 记录位置 和 对应的值 修改 到 区间的时候,我们可以通过 map 内置二分加速寻找,如果这个值已经不会被改变了,我们就把 它 从 map 中删除。
注意边界:
AC 代码如下:
/*
Make it simple and keep self stupid
author:Joanh_Lan
*/
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <numeric>
#include <cstring>
#include <cmath>
#include <map>
#include <unordered_map>
#include <bitset>
#include <set>
#include <random>
#include <ctime>
#include <queue>
#include <stack>
#include <climits>
#define buff \
ios::sync_with_stdio(false); \
cin.tie(0);
// #define int long long
#define ll long long
#define PII pair<int, int>
#define px first
#define py second
typedef std::mt19937 Random_mt19937;
Random_mt19937 rnd(time(0));
using namespace std;
const int mod = 1e9 + 7;
const int inf = 2147483647;
const int N = 100009;
// int Mod(int a,int mod){return (a%mod+mod)%mod;}
// int lowbit(int x){return x&-x;}//最低位1及其后面的0构成的数值
// int qmi(int a, int k, int p){int res = 1 % p;while (k){if (k & 1) res = Mod(res * a , p);a = Mod(a * a , p);k >>= 1;}return res;}
// int inv(int a,int mod){return qmi(a,mod-2,mod);}
// int lcm(int a,int b){return a*b/__gcd(a,b);}
int n, m;
map<int, int> mp;
ll sum = 0;
void solve()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
int tt; cin >> tt;
sum += tt;
mp[i] = tt;
}
mp[n + 1] = -1, mp[0] = -1;
while (m--)
{
int op; cin >> op;
if (op == 2)
cout << sum << '\n';
else
{
int l, r, k;
cin >> l >> r >> k;
for (auto it = mp.lower_bound(l); it->first <= r; it++)
{
int tk = k;
while (tk--)
{
int tt = round(10 * sqrtl(it->second));
sum = sum - it->second + tt;
it->second = tt;
if (tt == 0 || tt == 99 || tt == 100)
{
it = mp.erase(it);
it--;
break;
}
}
}
}
}
}
int main()
{
buff;
solve();
}