[BZOJ 2752] 高速公路
2024-09-01 12:47:06
Link:
Solution:
虽然有期望,但实际上就是除了个总数……
此题计算总代价明显还是要使用对每个$w_i$计算贡献的方式:
$w_i的贡献为w_i*(i-l+1)*(r-i)$(左端点的方案数乘上右端点的方案数)
为了能使维护的数据符合$RMQ$的性质,我们要将$l,r$分离出来,拆项得到:
$-w_i*i^2+w_i*i*(l+r-1)+w_i*(r-r*l)$
求完前缀和后用3棵线段树分别维护0/1/2次项的区间和即可
Code:
#include <bits/stdc++.h> using namespace std;
#define mid ((l+r)>>1)
#define lc k<<1,l,mid
#define rc k<<1|1,mid+1,r
typedef long long ll;
const int MAXN=1e5+;
char op[];
int n,m,l,r,v;
ll seg[MAXN<<][],tag[MAXN<<],s1[MAXN],s2[MAXN]; void merge(int k)
{for(int i=;i<;i++) seg[k][i]=seg[k<<][i]+seg[k<<|][i];} void modify(int k,int l,int r,ll inc)
{
tag[k]+=inc;
seg[k][]+=inc*(r-l+);
seg[k][]+=inc*(s1[r]-s1[l-]);
seg[k][]+=inc*(s2[r]-s2[l-]);
} void pushdown(int k,int l,int r)
{
if(!tag[k]) return;
modify(lc,tag[k]);modify(rc,tag[k]);
tag[k]=;
} void Update(int a,int b,int x,int k,int l,int r)
{
if(a<=l&&r<=b){modify(k,l,r,x);return;}
pushdown(k,l,r);
if(a<=mid) Update(a,b,x,lc);
if(b>mid) Update(a,b,x,rc);
merge(k);
} ll Query(int a,int b,int x,int k,int l,int r)
{
if(a<=l&&r<=b) return seg[k][x];
pushdown(k,l,r);
ll ret=;
if(a<=mid) ret+=Query(a,b,x,lc);
if(b>mid) ret+=Query(a,b,x,rc);
return ret;
} ll gcd(ll a,ll b)
{return (a%b==)?b:gcd(b,a%b);} int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
s1[i]=s1[i-]+i,s2[i]=s2[i-]+1ll*i*i;
while(m--)
{
scanf("%s%d%d",op,&l,&r);
if(op[]=='C')
scanf("%d",&v),Update(l,r-,v,,,n);
else
{
ll res=Query(l,r-,,,,n)*r*(-l)+Query(l,r-,,,,n)*(r+l-)-Query(l,r-,,,,n);
ll div=1ll*(r-l+)*(r-l)/;ll GCD=gcd(res,div);
printf("%lld/%lld\n",res/GCD,div/GCD);
}
}
return ;
}
最新文章
- Android Studio上NDK/JNI开发环境问题
- ios cordite 读取错误CoreData could not fulfill a fault for &#39;0x15b4a870
- 转 未能加载类型 xxxx
- linux设备驱动归纳总结(六):1.中断的实现【转】
- DIV隐藏与重显
- IDF 实验室部分题目WriteUp
- 马士兵 Servlet_JSP(3) Servlet和JSP的通信(源代码)
- 基于Andoird 4.2.2的Account Manager源代码分析学习:AccountManagerService系统服务的添加
- 2017最新PHP面试题
- MEAN 全栈开发 ——实现简单博客
- Unity3D AssetBundle的打包与加载
- ZJOI2019二试游记
- Oracle数据库执行exp命令--报参数&#39;log&#39; 不允许有多个值
- JavaScript模拟表单(带数组的复杂数据结构)提交
- Running Elixir in Docker Containers
- 通过blockchain_go分析区块链交易原理
- WAP 2.0开发XHTML MP语法及常用功能
- Python 水果统计
- Yii2自带验证码实现
- UNIX网络编程读书笔记:基本SCTP套接口编程