题目链接
题意分析
当前等级为\(x\)的魔法书会对等级在\([x,inf]\)的所有人造成\(y\)的影响
所以除了求平均值之外 就是区间修改区间求和
需要使用动态开点 + 标记永久化
需要注意的是 当前点为空的话 需要返回 目标区间长度*下放标记值
CODE:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<string>
#include<queue>
#include<map>
#include<stack>
#include<list>
#include<set>
#include<deque>
#include<vector>
#include<ctime>
#define ll long long
#define inf 0x7fffffff
#define N 200080
#define IL inline
#define M 10008611
#define D double
#define R register
using namespace std;
template<typename T>IL void read(T &_)
{
T __=0,___=1;char ____=getchar();
while(!isdigit(____)) {if(____=='-') ___=0;____=getchar();}
while(isdigit(____)) {__=(__<<1)+(__<<3)+____-'0';____=getchar();}
_=___ ? __:-__;
}
/*-------------OI使我快乐-------------*/
ll n,m,root,tot,maxn;
struct Node{
ll tag,sum;
Node(){tag=sum=0;}
}tre[M];
struct Qury{
ll knd,x,y;
}e[N];
ll lson[M],rson[M];
IL void update(ll &now,ll lenow,ll rinow,ll le,ll ri,ll d)
{
if(!now) now=++tot;tre[now].sum+=(ri-le+1)*d;
if(lenow==le&&rinow==ri)
{
tre[now].tag+=d;return;
}
ll mid=(lenow+rinow)>>1;
if(ri<=mid) update(lson[now],lenow,mid,le,ri,d);
else if(mid<le) update(rson[now],mid+1,rinow,le,ri,d);
else update(lson[now],lenow,mid,le,mid,d),update(rson[now],mid+1,rinow,mid+1,ri,d);
}
IL ll qury(ll now,ll lenow,ll rinow,ll le,ll ri,ll have)
{
if(!now) return (ri-le+1)*have;
if(le==lenow&&rinow==ri) return tre[now].sum+(rinow-lenow+1)*have;
ll mid=(lenow+rinow)>>1;
if(ri<=mid) return qury(lson[now],lenow,mid,le,ri,have+tre[now].tag);
else if(mid<le) return qury(rson[now],mid+1,rinow,le,ri,have+tre[now].tag);
else return qury(lson[now],lenow,mid,le,mid,have+tre[now].tag)+qury(rson[now],mid+1,rinow,mid+1,ri,have+tre[now].tag);
}
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
read(n);read(m);
for(R ll i=1;i<=n;++i)
{
read(e[i].x);read(e[i].y);
e[i].knd=-1;maxn=max(maxn,e[i].x);
}
for(R ll i=n+1;i<=n+m;++i)
{
read(e[i].knd);read(e[i].x);read(e[i].y);
if(e[i].knd==1) maxn=max(maxn,e[i].y);
else maxn=max(maxn,e[i].x);
}
for(R ll i=1;i<=n;++i)
{
update(root,1,maxn,e[i].x,maxn,e[i].y);
}
for(R ll i=n+1;i<=n+m;++i)
{
if(e[i].knd==1)
{
ll tmp=qury(root,1,maxn,e[i].x,e[i].y,0);
printf("%.4f\n",(1.0*(D)(tmp))/(1.0*(D)(e[i].y-e[i].x+1)));
}
else
{
update(root,1,maxn,e[i].x,maxn,e[i].y);
}
}
// fclose(stdin);
// fclose(stdout);
return 0;
}