1. 米小游的原石计划
为了抽到心爱的五星角色，米小游需要至少 n 颗原石。
目前米小游手里没有任何的原石，距离卡池结束还有 m 天。
原石有两种获取方式，一种是充小月卡，另一种是直接买。
1.充一次月卡需要 30 块钱，可以增加 30 天的祝福次数，每天只能领一次祝福（90原石），购买当天可额外领取 300原石。
2.直接买则是 1 块钱 10 原石。
为了尽可能省钱，他希望你帮他求出最少的花费。
其实也不用判断哪个方式更少，小于300直接购买，大于300必买月卡，因为直接给300
分类讨论模拟
int f(int n,int m){//n原石和m天数
//n大于等于30且m大于等于300必买月卡，转移成n-30，m-3000
//如果m小于300，买月卡不划算，直接用原石买
//如果m大于300且n小于30，判断使用月卡组合直接的方式，与直接购买方式
if(n<=0) return 0;
int cash = n/10 + (n%10>0);//直接购买的花费
if(n<300) return cash;
if(m>=30&&n>=300) return f(n-3000,m-30)+30;
int target = n-300-m*90;
int fee = 30;//组合方式购买费用
if(target>0) fee+= target/10+(target%10>0);
return min(fee,cash);
}
2. 米小游种树
一条长度为 n 的公路上，米小游雇佣了 m 名植树工，
其中第 i 位工人会给 [li,ri] 这一段区间中的每个点都种上一棵树。
但由于每个点最多种一棵树，因此如果某位工人发现自己要种的地方已经有树，
自己就会跳过这个点不管。米小游为了节约成本，现在要恰好少雇佣一名工人
，但同时他不希望少了此人会影响最终种树的结果，
现在请你帮他算算有多少名工人都可以成为恰好少雇佣的这一名呢。
万恶的资本家
因为每个查询都依赖其他的结果，所以无法通过离线的方式遍历
区间修改和查询使用线段树，修改完后，再对每个工人查询区间最小值是否大于1即可
因为没有边改边查，查询的数组是固定的，所以使用差分数组预先计算修改的区间，避免线段树引入懒标记
// 线段树节点结构体
struct TreeNode {
int left; // 节点区间左边界
int right; // 节点区间右边界
int value; // 节点存储的信息，这里以区间最值为例
};
void build(vector<int>& arr, vector<TreeNode>& tree, int index, int left, int right) {
tree[index].left = left;
tree[index].right = right;
// 叶子节点，存储输入数组的元素值
if (left == right) {
tree[index].value = arr[left];
return;
}
// 非叶子节点，递归构建左子树和右子树
int mid = (left + right) / 2;
build(arr, tree, index * 2 + 1, left, mid);//递归建左树
build(arr, tree, index * 2 + 2, mid + 1, right);//递归建右树
// 更新当前节点的信息，这里以区间最值为例
tree[index].value = min(tree[index * 2 + 1].value, tree[index * 2 + 2].value);
}
int query(vector<TreeNode>& tree, int index, int left, int right) {
if (tree[index].left == left && tree[index].right == right)
return tree[index].value;
else {
int mid = (tree[index].left + tree[index].right) / 2;
if (right <= mid)
return query(tree, index * 2 + 1, left, right);
else if (left > mid)
return query(tree, index * 2 + 2, left, right);
else
return min(query(tree, index * 2 + 1, left, mid), query(tree, index * 2 + 2, mid + 1, right));
}
}
int main() {
int n,m;
cin>>n>>m;
vector<vector<int>> area(m,vector<int>(2));
for(int i=0;i<m;i++){
cin>>area[i][0]>>area[i][1];
area[i][0]--;area[i][1]--;
}
vector<TreeNode> tree(4*n);
vector<int> arr(n,0);//这里需要使用差分数组进行初始化，避免线段树引入懒标记更新
vector<int> diff(n+1,0);
for(int i=0;i<m;i++){
diff[area[i][0]]++;
diff[area[i][1]+1]--;
}
int inc = 0;
for(int i=0;i<n;i++){//根据差分数组还原原始数组
inc = inc + diff[i];
arr[i] = arr[i]+inc;
}
build(arr, tree, 0, 0, n-1);
int res = 0;
for(int i=0;i<m;i++){
int l = area[i][0]; int r = area[i][1];
if(query(tree,0,l,r)>1) res++;
}
cout<<res;
return 0;
}
3. 米小游的数组询问
米小游有一个长度为 n 的数组 a ，她会询问 q 次，
每次会问你区间 [l,r] 中有多少个连续子数组包含 x 。
如果数组 a 可以通过从数组 b 的开头删除若干（可能为零或全部）元素以及从结尾删除若干（可能为零或全部）元素得到，
则数组 a 是数组 b 的子数组。
一眼标准贡献法的做法
不过还需要哈希+二分查找，不用栈来记录坐标
int main() {
int n;
cin>>n;
vector<int> nums(n);
unordered_map<int,vector<int>> m;
for(int i=0;i<n;i++){
cin>>nums[i];
m[nums[i]].push_back(i);//记录对应数的所有下标
}
int q;
cin>>q;
while(q--){
int l,r,x;
cin>>l>>r>>x;
l--;r--;
vector<int> &arr = m[x];
//需要查找l和r之间的所有下标，其实问题转化成了，找[l,r]范围内的区间
int begin = lower_bound(arr.begin(),arr.end(),l)-arr.begin();
int end = upper_bound(arr.begin(),arr.end(),r)-arr.begin()-1;
int res = 0;
int pre = l;
for(int i=begin;i<=end;i++){//这些下标里面的值都是可以选的值
int cur = arr[i];
res += (cur-pre+1)*(r-cur+1);
pre = cur;
}
cout<<res<<endl;
}
return 0;
}