生活随笔
收集整理的这篇文章主要介绍了
P3527 [POI2011]MET-Meteors 整体二分 + 树状数组
小编觉得挺不错的,现在分享给大家,帮大家做个参考.
洛谷
题意：
思路： 考虑整体二分前，一定要思考一下直接二分怎么做。显然对每个城市，当<pos<pos<pos的时候收集不够足够的陨石，>=pos>=pos>=pos的时候能收集足够多陨石，这个时候pospospos即为答案。这显然具有二分性，复杂度为O(NMlogM)O(NMlogM)O(NMlogM)。让后我们发现可以将所有城市放在一起二分，假设当前陨石落下波数区间为[l,r][l,r][l,r]，mid=l+r>>1mid=l+r>>1mid=l+r>>1，当前面[l,mid][l,mid][l,mid]陨石落下来的时候就足达到个城镇的预期的话，就把这个城镇放在左边，否则放在右边。让后将[l,mid][l,mid][l,mid]跟放在左边的城镇递归下去，[mid+1,r][mid+1,r][mid+1,r]跟放在右边的城镇递归下去。最终l==rl==rl==r的时候更新答案即可。
有可能存在无解的情况，我们只需要把初始的[1,k][1,k][1,k]改成[l,k+1][l,k+1][l,k+1]，等于k+1k+1k+1的时候无解。
还有一个要注意的点是代码的86行加到期望之后要停下来，不然可能会爆LL，因为这个调了一下午。
区间加，单点查询用树状数组应该不用多说了，用线段树可能会T。
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<map>
#include<cmath>
#include<cctype>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<sstream>
#include<ctime>
#include<cstdlib>
#define X first
#define Y second
#define L (u<<1)
#define R (u<<1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].l+tr[u].r>>1)
#define Len(u) (tr[u].r-tr[u].l+1)
#define random(a,b) ((a)+rand()%((b)-(a)+1))
#define db puts("---")
#define lowbit(x) ((x)&(-x))
using namespace std
;
typedef long long LL
;
typedef unsigned long long ULL
;
typedef pair
<int,int> PII
;const int N
=300010,mod
=1e9+7,INF
=0x3f3f3f3f;
const double eps
=1e-6;int n
,m
,k
;
LL s
[N
];
int p
[N
],p1
[N
],p2
[N
],ans
[N
];
struct Query
{LL l
,r
,c
,id
;
}q
[N
];
vector
<int>v
[N
];
LL tr
[N
<<2];void add(int x
,LL c
)
{for(int i
=x
;i
<=m
*2;i
+=lowbit(i
)) tr
[i
]+=c
;
}LL
sum(int x
)
{LL ans
=0;for(int i
=x
;i
;i
-=lowbit(i
)) ans
+=tr
[i
];return ans
;
}void solve(int l
,int r
,LL c
)
{if(l
<=r
) add(l
,c
),add(r
+1,-c
);else add(r
,c
),add(m
+1,-c
),add(1,c
),add(l
+1,-c
);
}void solve(int l
,int r
,int begin
,int end
)
{int mid
=l
+r
>>1;if(l
==r
){for(int i
=begin
;i
<=end
;i
++){int id
=p
[i
];ans
[id
]=l
;}return;}for(int i
=l
;i
<=mid
;i
++) add(q
[i
].l
,q
[i
].c
),add(q
[i
].r
+1,-q
[i
].c
);int cnt1
,cnt2
; cnt1
=cnt2
=0;for(int i
=begin
;i
<=end
;i
++){int id
=p
[i
];LL ssum
=0;for(int j
=0;j
<v
[id
].size()&&ssum
<s
[id
];j
++) ssum
+=sum(v
[id
][j
])+sum(v
[id
][j
]+m
);if(ssum
>=s
[id
]) p1
[++cnt1
]=p
[i
];else p2
[++cnt2
]=p
[i
],s
[id
]-=ssum
;}for(int i
=l
;i
<=mid
;i
++) add(q
[i
].l
,-q
[i
].c
),add(q
[i
].r
+1,q
[i
].c
);for(int i
=1;i
<=cnt1
;i
++) p
[begin
+i
-1]=p1
[i
];for(int i
=1;i
<=cnt2
;i
++) p
[begin
+cnt1
+i
-1]=p2
[i
];solve(l
,mid
,begin
,begin
+cnt1
-1); solve(mid
+1,r
,begin
+cnt1
,end
);
}template <class T>
bool read(T
&ret
)
{char c
;int sgn
;T bit
=0.1;if(c
=getchar(), c
==EOF)return 0;while(c
!='-' && c
!='.' && (c
<'0' || c
>'9'))c
=getchar();sgn
=(c
=='-')? -1:1;ret
=(c
=='-')? 0:(c
-'0');while(c
=getchar(), c
>='0' && c
<='9')ret
=ret
*10+(c
-'0');if(c
==' ' || c
=='\n'){ret
*=sgn
;return 1;}while(c
=getchar(), c
>='0' && c
<='9')ret
+=(c
-'0')*bit
, bit
/=10;ret
*=sgn
;return 1;
}inline void out(int x
)
{if(x
>9)out(x
/10);putchar(x
%10+'0');
}int main()
{
read(n
); read(m
);for(int i
=1;i
<=m
;i
++){int x
; read(x
);v
[x
].pb(i
);}for(int i
=1;i
<=n
;i
++) p
[i
]=i
;for(int i
=1;i
<=n
;i
++) read(s
[i
]);read(k
);for(int i
=1;i
<=k
;i
++){int l
,r
,c
; read(l
); read(r
); read(c
);if(l
>r
) r
+=m
;q
[i
]={l
,r
,c
,i
};}solve(1,k
+1,1,n
);for(int i
=1;i
<=n
;i
++) (ans
[i
]==k
+1)? puts("NIE"):printf("%d\n",ans
[i
]);return 0;
}
总结
以上是生活随笔为你收集整理的P3527 [POI2011]MET-Meteors 整体二分 + 树状数组的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。
