Link:

BZOJ 2752 传送门

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 ;
}

最新文章

  1. Android Studio上NDK/JNI开发环境问题
  2. ios cordite 读取错误CoreData could not fulfill a fault for &#39;0x15b4a870
  3. 转 未能加载类型 xxxx
  4. linux设备驱动归纳总结(六):1.中断的实现【转】
  5. DIV隐藏与重显
  6. IDF 实验室部分题目WriteUp
  7. 马士兵 Servlet_JSP(3) Servlet和JSP的通信(源代码)
  8. 基于Andoird 4.2.2的Account Manager源代码分析学习:AccountManagerService系统服务的添加
  9. 2017最新PHP面试题
  10. MEAN 全栈开发 ——实现简单博客
  11. Unity3D AssetBundle的打包与加载
  12. ZJOI2019二试游记
  13. Oracle数据库执行exp命令--报参数&#39;log&#39; 不允许有多个值
  14. JavaScript模拟表单(带数组的复杂数据结构)提交
  15. Running Elixir in Docker Containers
  16. 通过blockchain_go分析区块链交易原理
  17. WAP 2.0开发XHTML MP语法及常用功能
  18. Python 水果统计
  19. Yii2自带验证码实现
  20. UNIX网络编程读书笔记:基本SCTP套接口编程

热门文章

  1. codeforces 1015A
  2. bzoj1914 [Usaco2010 OPen]Triangle Counting 数三角形 计算机和
  3. 使用fuser查询文件、目录、socket端口的占用进程
  4. PHP设计模式-代理模式
  5. 转: 构建基于Nginx的文件服务器思路与实现
  6. Java输入输出流备忘
  7. request.getParameterValues与request.getParameter的区别
  8. JGroups 初探
  9. Android的简单应用(四)——字符串处理
  10. OpenCV——Mat、CvMat、IplImage类型浅析【转】