线段树+概率

今天这道题爆零了,奥妙重重。

其实我们可以把式子化成这样:sigma((i-l+1)*(r-i+1)*ai) 这里r减了1

然后展开,(1-l)*(r+1)*ai+(r+l)*i*ai-i*i*ai

我们发现除了含有i的项其他都可以提到外面,也就是说我们要维护ai,i*ai,i*i*ai三个量。

那么就用线段树维护,打标记时用数列公式即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = ;
int n, m;
struct seg {
ll tag[N << ], tree[N << ][];
void pushdown(int x, int l, int r)
{
if(!tag[x]) return;
tag[x << ] += tag[x];
tag[x << | ] += tag[x];
int mid = (l + r) >> ;
tree[x << ][] += tag[x] * (ll)(mid - l + 1ll);
tree[x << | ][] += tag[x] * (ll)(r - mid);
tree[x << ][] += tag[x] * (ll)(l + mid) * (ll)(mid - l + ) / 2ll;
tree[x << | ][] += tag[x] * (ll)(r + mid + 1ll) * (ll)(r - mid) / 2ll;
tree[x << ][] += tag[x] * ((ll)mid * (ll)(mid + 1ll) * (ll)(2ll * mid + 1ll) - (ll)(l - 1ll) * (ll)l * (ll)(2ll * l - 1ll)) / 6ll;
tree[x << | ][] += tag[x] * ((ll)r * (ll)(r + 1ll) * (ll)(2ll * r + 1ll) - (ll)mid * (ll)(mid + 1ll) * (ll)(2ll * mid + 1ll)) / 6ll;
tag[x]= 0ll;
}
void update(int l, int r, int x, int a, int b, ll delta)
{
if(l > b || r < a) return;
if(l >= a && r <= b)
{
tag[x] += delta;
tree[x][] += (ll)(r - l + 1ll) * delta;
tree[x][] += (ll)(l + r) * (ll)(r - l + ) / 2ll * delta;
tree[x][] += ((ll)r * (ll)(r + 1ll) * (2ll * r + ) - (ll)(l - 1ll) * (ll)l * (ll)(2ll * l - 1ll)) / 6ll * delta;
return;
}
pushdown(x, l, r);
int mid = (l + r) >> ;
update(l, mid, x << , a, b, delta);
update(mid + , r , x << | , a, b, delta);
for(int i = ; i <= ; ++i)
tree[x][i] = tree[x << ][i] + tree[x << | ][i];
}
ll query(int l, int r, int x, int a, int b, int type)
{
if(l > b || r < a) return 0ll;
if(l >= a && r <= b) return tree[x][type];
pushdown(x, l, r);
int mid = (l + r) >> ;
return (query(l, mid, x << , a, b, type) + (query(mid + , r, x << | , a, b, type)));
}
} t;
ll gcd(ll a, ll b)
{
return !b ? a : gcd(b, a % b);
}
int main()
{
// freopen("c.in", "r", stdin);
// freopen("c.out", "w", stdout);
scanf("%d%d", &n, &m);
--n;
while(m--)
{
char s[]; int l, r; ll delta; scanf("%s", s);
if(s[] == 'C')
{
scanf("%d%d%lld", &l , &r, &delta);
--r;
t.update(, n, , l, r, delta);
}
if(s[] == 'Q')
{
scanf("%d%d", &l, &r);
--r;
ll T1 = t.query(, n, , l, r, );
ll T2 = t.query(, n, , l, r, );
ll T3 = t.query(, n, , l, r, );
ll ans = (ll)(1ll - l) * (ll)(r + 1ll) * T1 + (ll)(r + l) * T2 - T3;
ll T4 = (ll)(r - l + 2ll) * (ll)(r - l + 1ll) / 2ll;
ll T = gcd(ans, T4);
printf("%lld/%lld\n", ans / T, T4 / T);
}
}
// fclose(stdin); fclose(stdout);
return ;
}

最新文章

  1. 利用private font改变PDF文件的字体
  2. JNI常见错误整理
  3. 查看LINUX进程内存占用情况(转)
  4. ArcGIS使用Python脚本工具
  5. QT中可以用QProgressBar或着QProgressDialog来实现进度条
  6. JqueryMobile- 搭建主模板
  7. Php RSS
  8. sendto() 向广播地址发包返回errno 13, Permission denied错误
  9. 条码的种类(types of barcode)
  10. QNX---Interrupt vector numbers(原创!!!)
  11. Requests卡死问题
  12. js:基于原生js的上啦下啦刷新功能
  13. windows yii2 配置redis
  14. QueryRunner使用之可变条件的处理
  15. tensorflow实现基于LSTM的文本分类方法
  16. Python实现正则表达式匹配任意的邮箱
  17. 『Numpy』内存分析_高级切片和内存数据解析
  18. copy GC 和 mark &amp; compaction GC的算法异同
  19. PAT A1004 Counting Leaves (30 分)——树,DFS,BFS
  20. strlen()与mb_strlen()的区别

热门文章

  1. java面试题链接
  2. QQ浏览器占用资源真的大
  3. 51nod 1118 机器人走方格【dp】
  4. LINUX-关机 (系统的关机、重启以及登出 )
  5. Html5离线缓存简介
  6. python 类、模块、包的区别
  7. javascript 事件对象(event 对象)
  8. ssh连接失败
  9. python 元组不变 列表可变
  10. win7下登入本機、域的正確方法