bzoj2752
2024-08-31 00:13:54
线段树+概率
今天这道题爆零了,奥妙重重。
其实我们可以把式子化成这样: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 ;
}
最新文章
- 利用private font改变PDF文件的字体
- JNI常见错误整理
- 查看LINUX进程内存占用情况(转)
- ArcGIS使用Python脚本工具
- QT中可以用QProgressBar或着QProgressDialog来实现进度条
- JqueryMobile- 搭建主模板
- Php RSS
- sendto() 向广播地址发包返回errno 13, Permission denied错误
- 条码的种类(types of barcode)
- QNX---Interrupt vector numbers(原创!!!)
- Requests卡死问题
- js:基于原生js的上啦下啦刷新功能
- windows yii2 配置redis
- QueryRunner使用之可变条件的处理
- tensorflow实现基于LSTM的文本分类方法
- Python实现正则表达式匹配任意的邮箱
- 『Numpy』内存分析_高级切片和内存数据解析
- copy GC 和 mark &; compaction GC的算法异同
- PAT A1004 Counting Leaves (30 分)——树,DFS,BFS
- strlen()与mb_strlen()的区别