首页 > 其他分享 >树状数组【单点修改+区间查询】+二分

树状数组【单点修改+区间查询】+二分

时间:2025-01-13 10:54:41浏览次数:1  
标签:二分 单点 树状 int ll while query sum const

https://codeforces.com/gym/580226/problem/H

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define lowbit(x)  x&(-x)
using ll = long long;
using pii = pair<int, int>;
const double PI = acos(-1);
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
ll c[N];
int a[N];
int n;
void add_dandian(int x,int k){
	for(int i=x;i<=n;i+=lowbit(i)){
		c[i]+=k;
	}
}
ll query(int l,int r){
	ll sum=0;
	for(int i=r;i;i-=lowbit((i)))
		sum+=c[i];
	for(int i=l-1;i;i-=lowbit(i))
		sum-=c[i];
	return sum;
}
void solve() {
	
	ll T;
	cin>>n>>T;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		add_dandian(i,a[i]);
	}
	ll ans=0;
	int cnt=n;
	while(query(1,n)){//当前不能选这颗糖,以后也选不了
		ll sum=query(1,n);
		ans+=T/sum*cnt;//当前的这些糖能选几轮
		T-=T/sum*sum;
		while(1){
			int l=1,r=n;
			while(l<r){//二分找第一个不能选的糖,删除
				int mid=(l+r)>>1;
				if(query(1,mid)>T) r=mid;
				else l=mid+1;
			}
			if(l==n&&query(1,n)<=T) break;
			else{
				cnt--;
				add_dandian(l,-a[l]);//选不了单点查询删除
			}
		}
	}
	cout<<ans;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	
	int T = 1;
//	cin>>T;
	while (T--) {
		solve();
	}
	
	return 0;
}

标签:二分,单点,树状,int,ll,while,query,sum,const
From: https://www.cnblogs.com/laileou/p/18668192

相关文章

  • 树状数组【区间修改+单点查询】
    https://www.luogu.com.cn/problem/P3368#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'#definelowbit(x)x&(-x)usingll=longlong;usingpii=pair<int,int>;constdoublePI=acos(-1);constintN=5e5+10......
  • 树状数组【模板】
    https://www.luogu.com.cn/problem/P3374#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'#definelowbit(x)x&(-x)usingll=longlong;usingpii=pair<int,int>;constdoublePI=acos(-1);constintN=5e5+10......
  • 算法-在数组中获取制定值的索引值-php(二分法)
    算法-在数组中获取制定值的索引值-php(二分法)<?php/***代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可***@paramnumsint整型一维数组*@paramtargetint整型*@returnint整型*/functionsearch($nums,$target){//......
  • E - Simultaneous Kagamimochi (二分答案+贪心)
    题目链接:https://atcoder.jp/contests/abc388/tasks/abc388_e题意:给定一个数组,当数组中一个数的两倍不超过另一个数时,认为这两个数可以组成一对,(组合后这两个数无法再次进行组合),求最大组合数思路:如果能条件能满足k对,一定能满足k-1对。同时尽量让小的和大的里面相对小的组合......
  • 洛谷 P1102 A-B 数对(二分写法)
    题目:P1102A-B数对-洛谷|计算机科学教育新生态题目背景出题是一件痛苦的事情!相同的题目看多了也会有审美疲劳,于是我舍弃了大家所熟悉的A+BProblem,改用A-B了哈哈!题目描述给出一串正整数数列以及一个正整数 C,要求计算出所有满足 A−B=C 的数对的个数(不同位置的数......
  • 轻松实现单点登录(SSO):基于 Keycloak 的 OIDC 与 OAuth 2.0 完整指南
    言简意赅的讲解KeycloakOIDC与OAuth2.0解决的痛点Keycloak是一款开源的身份和访问管理(IAM)工具,支持多种协议,包括OIDC(OpenIDConnect)、OAuth2.0、SAML等。它简化了身份认证与授权流程,提供了集中管理用户、角色、权限等功能,常被用作企业或微服务体系下的统一认证中心......
  • 寻找重复数(二分查找)
    给定一个包含 n+1 个整数的数组 nums ,其数字都在 [1,n] 范围内(包括 1 和 n),可知至少存在一个重复的整数。假设 nums 只有 一个重复的整数 ,返回 这个重复的数 。你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。 示例1:输入:num......
  • 二分+排序
    https://codeforces.com/contest/2053/problem/Dhttps://blog.csdn.net/weixin_61825750/article/details/144799098#include<bits/stdc++.h>#definelcp<<1#definercp<<1|1#defineINF2e9usingnamespacestd;#defineendl'\n'us......
  • wqs二分的一些性质和细节
    wqs二分共线情况的处理在我们进行\(wqs\)二分时,需要要求函数是具有凸性的,但是有时候最终所求的点在函数上可能和前后的几个点共线,这时我们在应该如何更新答案呢?此时的取值方式和你二分的\(check\)写法有关。我们以上凸壳为例:\(check\)会对每个斜率求出一个转移的次数。......
  • 树状数组
    回顾一下以前不太明白的树状数组原理。以@Gcint-since2024大佬做的总结为参考。\(lowbit(x)\)表示\(x\)在二进制表示下从右往左第一个\(1\)及其后所有的\(0\)构成的数。记\(a[x]\)为原数组,\(tree[x]\)为树状数组:定义\(tree[x]\)表示以\(a[x]\)结尾,长度为......