#1034 : 毁灭者问题
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
在 Warcraft III 之冰封王座中，毁灭者是不死族打三本后期时的一个魔法飞行单位。
毁灭者的核心技能之一，叫做魔法吸收（Absorb Mana）：
现在让我们来考虑下面的问题：
假设你拥有 n 个魔法单位，他们从左到有站在一行，编号从 1 到 n。 每个单位拥有三项属性：
-
si: 初始法力。
-
mi: 最大法力上限。
-
ri: 每秒中法力回复速度。
现在你操纵一个毁灭者，有 m 个操作，t l r，表示时刻 t，毁灭者对所有编号从 l 到 r 的单位，使用了魔法吸收。操作按照时间顺序给出，计算毁灭者一共吸收了多少法力。
输入
输入数据的第一行有一个整数 n(1 ≤ n ≤105) — 你的魔法单位的数目。
接下来的 n 行，每行有三个整数 si, mi, ri(0 ≤ si ≤ mi ≤ 105, 0 ≤ ri ≤ 105) 描述一个魔法单位。
接下来一行又一个整数 m(1 ≤ m ≤ 105)， — 操作的数目。
接下来的 m 行，每行描述一个操作 t, l, r(0 ≤ t ≤ 109, 1 ≤ l ≤ r ≤ n)，t 非降。
输出
输出一行一个整数表示毁灭者一共吸收了多少法力。
- 样例输入
-
5 0 10 1 0 12 1 0 20 1 0 12 1 0 10 1 2 5 1 5 19 1 5
- 样例输出
- 83
- 题解：
- 自己写了一棵线段树的做法，看了网上一篇辣鸡博客，哎，无语了，
- 自己写的时候是知道的这个写法比暴力还暴力，n^2logn的，但是还是
- 写了，结果TLE，T飞了。
- 附上T飞代码
1 #include<cstring> 2 #include<cmath> 3 #include<algorithm> 4 #include<iostream> 5 #include<cstdio> 6 7 #define N 100007 8 #define ll long long 9 using namespace std; 10 inline int read() 11 { 12 int x=0,f=1;char ch=getchar(); 13 while(ch<'0'||ch>'9'){if (ch=='-')f=-1;ch=getchar();} 14 while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} 15 return x*f; 16 } 17 18 int n,m; 19 ll ans; 20 struct Node 21 { 22 ll t,m,r,s; 23 }tr[N*4]; 24 25 inline void update(int p) 26 { 27 tr[p].s=tr[p<<1].s+tr[p<<1|1].s; 28 } 29 void build(int p,int l,int r) 30 { 31 if (l==r) 32 { 33 tr[p].s=read(),tr[p].m=read(),tr[p].r=read(); 34 tr[p].t=0; 35 return; 36 } 37 int mid=(l+r)>>1; 38 build(p<<1,l,mid),build(p<<1|1,mid+1,r); 39 update(p); 40 } 41 void renew(int p,int l,int r,int x,int y,int t) 42 { 43 if (l==r) 44 { 45 if (tr[p].s+(t-tr[p].t)*tr[p].r>tr[p].m) tr[p].s=tr[p].m; 46 else tr[p].s+=(t-tr[p].t)*tr[p].r; 47 tr[p].t=t; 48 return; 49 } 50 int mid=(l+r)>>1; 51 if (y<=mid) renew(p<<1,l,mid,x,y,t); 52 else if (x>mid) renew(p<<1|1,mid+1,r,x,y,t); 53 else renew(p<<1,l,mid,x,mid,t),renew(p<<1|1,mid+1,r,mid+1,y,t); 54 update(p); 55 } 56 ll query(int p,int l,int r,int x,int y) 57 { 58 if (l==x&&y==r) return tr[p].s; 59 int mid=(l+r)>>1; 60 if (y<=mid) return query(p<<1,l,mid,x,y); 61 else if (x>mid) return query(p<<1|1,mid+1,r,x,y); 62 else return query(p<<1,l,mid,x,mid)+query(p<<1|1,mid+1,r,mid+1,y); 63 } 64 void clean_all(int p,int l,int r,int x,int y) 65 { 66 if (l==r) 67 { 68 tr[p].s=0; 69 return; 70 } 71 int mid=(l+r)>>1; 72 if (y<=mid) return clean_all(p<<1,l,mid,x,y); 73 else if (x>mid) return clean_all(p<<1|1,mid+1,r,x,y); 74 else clean_all(p<<1,l,mid,x,mid),clean_all(p<<1|1,mid+1,r,mid+1,y); 75 update(p); 76 } 77 int main() 78 { 79 freopen("fzy.in","r",stdin); 80 freopen("fzy.out","w",stdout); 81 82 n=read(),build(1,1,n); 83 m=read(); 84 for (int i=1;i<=m;i++) 85 { 86 int t=read(),x=read(),y=read(); 87 renew(1,1,n,x,y,t); 88 ans+=query(1,1,n,x,y); 89 clean_all(1,1,n,x,y); 90 } 91 printf("%lld",ans); 92 }
正解思路
对于s,m,r我们可以这样想，
对于输入的间隔tk-tk-1，设为d，如果d*r>m 则为m 1
如果d*r<=m，则为r*d 2
所以答案就等于所以人，满足1的个数乘以m，以及满足2的∑di *r，这个就是答案。
我们应该对于每个人来计算答案，对于每个人，如果暴力计算的话，就是O（nm）对吧。
还是T飞，那怎么办呢，可以用一棵平衡树+线段树来维护，对于每个起始时间，结束时间
都放入平衡树中，间隔即为判断条件，可以放入线段树中，结束时间时在维护，一下，删除
所以，每个询问只会被插入一次，删除一次，对于每个人询问一次，所以总复杂度为O（nlgn）。
代码，莫名wrong，但是对拍没有错，就精神ac吧。
1 #include<cstring> 2 #include<cmath> 3 #include<algorithm> 4 #include<cstdio> 5 #include<iostream> 6 #include<set> 7 #include<vector> 8 9 #define lson tr[p].ls 10 #define rson tr[p].rs 11 #define z1 set<int>::iterator 12 #define N 100007 13 #define ll long long 14 using namespace std; 15 inline int read() 16 { 17 int x=0,f=1;char ch=getchar(); 18 while(ch<'0'||ch>'9'){if (ch=='-')f=-1;ch=getchar();} 19 while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} 20 return x*f; 21 } 22 23 int n,m,root,sz; 24 ll ans; 25 vector<int>hd[N],ed[N]; 26 set<int>q;//哪几个时间段有 27 struct Node 28 { 29 ll s,m,r; 30 }a[N]; 31 struct Date 32 { 33 int num,sum,ls,rs; 34 }tr[10000007]; 35 36 inline void update(int p) 37 { 38 tr[p].sum=tr[lson].sum+tr[rson].sum; 39 tr[p].num=tr[lson].num+tr[rson].num; 40 } 41 void add(int &p,int l,int r,int x,int flag) 42 { 43 if(!p) p=++sz; 44 if (l==r) 45 { 46 tr[p].sum+=x*flag,tr[p].num+=flag; 47 return; 48 } 49 int mid=(l+r)>>1; 50 if (x<=mid) add(lson,l,mid,x,flag); 51 else add(rson,mid+1,r,x,flag); 52 update(p); 53 } 54 ll query1(int p,int l,int r,int x,int y) 55 { 56 if (!p) return 0; 57 if (l==x&&r==y) return tr[p].sum; 58 int mid=(l+r)>>1; 59 if (y<=mid) return query1(lson,l,mid,x,y); 60 else if (x>mid) return query1(rson,mid+1,r,x,y); 61 else return query1(lson,l,mid,x,mid)+query1(rson,mid+1,r,mid+1,y); 62 } 63 ll query2(int p,int l,int r,int x,int y) 64 { 65 if (!p) return 0; 66 if (l==x&&r==y) return tr[p].num; 67 int mid=(l+r)>>1; 68 if (y<=mid) return query2(lson,l,mid,x,y); 69 else if (x>mid) return query2(rson,mid+1,r,x,y); 70 else return query2(lson,l,mid,x,mid)+query2(rson,mid+1,r,mid+1,y); 71 } 72 int main() 73 { 74 freopen("fzy.in","r",stdin); 75 freopen("solution.out","w",stdout); 76 77 n=read(); 78 for (int i=1;i<=n;i++) 79 a[i].s=read(),a[i].m=read(),a[i].r=read(); 80 m=read(); 81 for (int i=1;i<=m;i++) 82 { 83 int t=read(),x=read(),y=read(); 84 hd[x].push_back(t); 85 ed[y].push_back(t); 86 } 87 q.insert(-1),q.insert(1e9+7);//放一个哨兵。 88 89 for (int i=1;i<=n;i++) 90 { 91 for (int j=0;j<hd[i].size();j++) 92 { 93 z1 qq=q.lower_bound(hd[i][j]),hj=q.upper_bound(hd[i][j]);qq--; 94 if (*qq==-1&&*hj==1e9+7) q.insert(hd[i][j]); 95 else if (*qq==-1) 96 { 97 q.insert(hd[i][j]); 98 add(root,0,1000000000,*hj-hd[i][j],1); 99 } 100 else if (*hj==1e9+7) 101 { 102 q.insert(hd[i][j]); 103 add(root,0,1000000000,hd[i][j]-*qq,1); 104 //cout<<hd[i][j]-*qq<<" flag"<<endl; 105 } 106 else 107 { 108 add(root,0,1000000000,*hj-*qq,-1); 109 q.insert(hd[i][j]); 110 add(root,0,1000000000,hd[i][j]-*qq,1),add(root,0,1000000000,*hj-hd[i][j],1); 111 } 112 } 113 int up=ceil(a[i].m*1.0/(double)a[i].r); 114 ans+=query1(root,0,1000000000,0,up-1)*a[i].r; 115 ans+=query2(root,0,1000000000,up,1000000000)*a[i].m; 116 z1 t=q.begin();t++; 117 if (*t!=1000000007) 118 { 119 if (*t*a[i].r+a[i].s>a[i].m) ans+=a[i].m; 120 else ans+=*t*a[i].r+a[i].s; 121 } 122 for (int j=0;j<ed[i].size();j++) 123 { 124 z1 qq=q.lower_bound(ed[i][j]),hj=q.upper_bound(ed[i][j]);qq--; 125 if (*qq==-1&&*hj==1e9+7) q.erase(ed[i][j]); 126 else if (*qq==-1) 127 { 128 q.erase(ed[i][j]); 129 add(root,0,1000000000,*hj-ed[i][j],-1); 130 } 131 else if (*hj==1e9+7) 132 { 133 q.erase(ed[i][j]); 134 add(root,0,1000000000,ed[i][j]-*qq,-1); 135 } 136 else 137 { 138 add(root,0,1000000000,ed[i][j]-*qq,-1),add(root,0,1000000000,*hj-ed[i][j],-1); 139 q.erase(ed[i][j]); 140 add(root,0,1000000000,*hj-*qq,1); 141 } 142 } 143 // cout<<ans<<endl; 144 } 145 printf("%lld",ans); 146 }