B题注意到每次都会至少下降1，所以不会超过30次，直接O(30n)即可
C题感觉可能比D和F还要思维一些。
肯定是尽量多积累combo一些然后一次清空，那么我们能清空的最大值就是当前的最大值，所以每次用小的来累计combo，然后消除当前的最大值，即使小的那些不是一整段也没有关系，然后就是一些特判。复杂度O(n)
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<set>
#define A puts("YES")
#define B puts("NO")
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
using namespace std;
typedef double db;
typedef long long ll;
const int mo=998244353;
//const int inf=1<<30;
const int N=2e5+5;
ll n,a[N],siz,ans;
int main()
{
// freopen("data.in","r",stdin);
// freopen("ans.out","w",stdout);
int T;
scanf("%d",&T);
while (T--){
scanf("%lld",&n);
fo(i,1,n) scanf("%lld",&a[i]);
sort(a+1,a+n+1);
ans=0;
int j=1;
siz=n;
ll s;
while (1) {
if (!a[j]) j++;
if (j>n) break;
if (j==n) {
if (!a[n]) break;
if (a[n]==1) ans++;
else if (a[n]&1) ans+=a[n]/2+2;
else ans+=a[n]/2+1;
break;
}
s=a[j];
while (j+1<n && s<a[n]) j++,s+=a[j];
if (s<a[n]) {
ans+=s;
if (a[n]==s+1) ans+=2;
else if ((a[n]+s)%2) ans+=(a[n]-s)/2+2;
else ans+=(a[n]-s)/2+1;
break;
}
ans+=a[n]+1;
a[j]=(s-a[n]);
n--;
}
printf("%lld\n",ans);
}
return 0;
}
D题感觉没什么好说的，直接两个log就完事了。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<set>
#include<map>
#include<vector>
#define A puts("Yes")
#define B puts("No")
#define fo(i,a,b) for (ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
using namespace std;
typedef double db;
typedef long long ll;
typedef __int128 i128;
const ll mo = 1e9 + 7;
const int N = 2e5 + 5;
// const ll inf = 2e18;
ll d, u, ans;
ll b[100];
void solve(ll x, ll d, ll u) {
ll l, r, mid;
ll now = 1, tot = 0;
while ((i128)now * (i128)x <= u) now *= x, tot++;
for (ll i = u;i <= u;i = l + 1) {
l = i; r = d;
while ((i128)now * (i128)x <= i) now *= x, tot++;
while (l < r) {
mid = (l + r + 1) >> 1;
if (mid <= (i128)now * (i128)x) l = mid;
else r = mid - 1;
}
ans += (l - i + 1) * tot;
}
}
int main()
{
// #ifdef LOCAL
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
// #endif
b[0] = 1;
fo(i, 1, 60) b[i] = b[i - 1] * 2ll;
int T;
scanf("%d", &T);
while (T--) {
ans = 0;
scanf("%lld %lld", &d, &u);
fo(i, 2, 60) {
if (b[i] > u) break;
// if (b[i] < d) continue;
solve(i, max(d, b[i]), min(u, b[i + 1] - 1));
}
printf("%lld\n", ans);
}
return 0;
}
F是个非常经典的套路，假如没有时间的限制，那么就是直接利用用差分+dfs序套个fenwick树就行，加上时间限制也简单，直接将询问倒着做就行，在一个点被加入的时候计算它的答案。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<set>
#define A puts("YES")
#define B puts("NO")
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
using namespace std;
typedef double db;
typedef long long ll;
const int mo=998244353;
//const int inf=1<<30;
const int N=5e5+5;
struct node{
int t,x,v,y;
};
node q[N];
int n,m;
int head[N],to[N],nex[N],tot;
int l[N],r[N],cnt;
ll c[N],y,x,ans[N];
int lowbit(int x){
return x&(-x);
}
void upd(int x,ll y){
for (;x<N;x+=lowbit(x)) c[x]+=y;
}
ll ask(int x){
ll s=0;
for (;x;x-=lowbit(x)) s+=c[x];
return s;
}
void add(int x,int y){
to[++tot]=y; nex[tot]=head[x]; head[x]=tot;
}
void dfs(int x){
ans[x]=0;
l[x]=r[x]=++cnt;
for (int i=head[x];i;i=nex[i]){
int v=to[i];
dfs(v);
r[x]=max(r[x],r[v]);
}
}
int main()
{
// freopen("data.in","r",stdin);
// freopen("ans.out","w",stdout);
int T;
scanf("%d",&T);
while (T--){
scanf("%d",&m);
n=1;
head[1]=0;
tot=0;
fo(i,1,m) {
scanf("%d",&q[i].t);
if (q[i].t==1) {
scanf("%d",&q[i].x);
n++;
add(q[i].x, n);
q[i].y=n;
head[n]=0;
}
else {
// R(q[i].x); R(q[i].v);
scanf("%d %d",&q[i].x, &q[i].v);
}
}
cnt=0;
dfs(1);
fo(i,1,n+3) c[i]=0;
fd(i,m,1) {
if (q[i].t==1) {
ans[q[i].y]=ask(l[q[i].y]);
}
else {
x=q[i].x; y=q[i].v;
upd(l[x], y);
upd(r[x]+1, -y);
}
}
ans[1]=ask(1);
fo(i,1,n) printf("%lld ",ans[i]);
printf("\n");
}
return 0;
}