【CodeChef】LCH15JGH Many bananas
发布时间
阅读量：
阅读量
该程序通过数据结构和算法高效地处理输入数据并进行快速查询与更新操作。第一部分（BIT类）使用位运算优化方法实现快速求和与点更新操作；第二部分（线性筛法）通过分块策略减少计算复杂度，在大数据量下表现更优。程序支持三种操作：计算总值、单点增1、单点减1并调整结构以维护最大值信息。
暴力可以水过。
#include<bits/stdc++.h>
using namespace std;
char inc;
inline void get(int& x)
{
x = 0;inc = getchar();
while(!isdigit(inc))inc=getchar();
while(isdigit(inc))
{
x=x*10+inc-'0';
inc=getchar();
}
}
#define maxn 100010
int n,m,a[maxn],vmax;
char op[2];
int main()
{
get(n);
int x,y;
for(int i=1;i<=n;i++)
{
get(x);get(y);
a[x] = y;
vmax = max(vmax,x);
}
get(m);
for(int i=1;i<=m;i++)
{
scanf("%s",op);get(x);
if(*op=='?')
{
long long tot = 0;
for(int j=2;j<=vmax;j++)
{
tot+=(x%j)*(long long)a[j];
}
printf("%lld\n",tot);
}
else if(*op=='+')
{
a[x]++;vmax=max(vmax,x);
}
else
{
a[x]--;
for(int j=vmax;j>=1;j--)
if(a[j])
{
vmax = j;
break;
}
}
}
return 0;
}BIT
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#define ll long long
#define inf 1000000000
using namespace std;
ll read()
{
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int n,m;
ll tot;
ll t[100005],c[305];
void add(int x,ll val)
{
for(int i=x;i<=100000;i+=i&-i)
t[i]+=val;
}
ll query(int x)
{
ll ans=0;
for(int i=x;i;i-=i&-i)
ans+=t[i];
return ans;
}
void solve_add(int x,ll val)
{
if(x<=300)c[x]+=val;
else
{
tot+=val;
for(int i=x;i<=100000;i+=x)
add(i,val*(-x));
}
}
ll solve_query(ll x)
{
ll ans=0;
for(int i=1;i<=300;i++)
ans+=x%i*c[i];
ans=ans+tot*x+query(x);
return ans;
}
int main()
{
n=read();
int x,y;char ch[2];
for(int i=1;i<=n;i++)
{
x=read();y=read();
solve_add(x,y);
}
m=read();
while(m--)
{
scanf("%s",ch+1);
x=read();
if(ch[1]=='?')printf("%lld\n",solve_query(x));
else if(ch[1]=='+')solve_add(x,1);
else solve_add(x,-1);
}
return 0;
}全部评论 (0)
还没有任何评论哟~