题目链接:http://codeforces.com/contest/1257/problem/D
题目大意:
有n个怪物,每个怪物都有一个能力值a。有m个勇士,每个勇士都有一个力量P和耐力S。明天可以选择一个勇士去打怪物,必须按顺序打,如果这个勇士的能力P>=a那么就可以打败这个怪物,就必须打下一个怪物,而且最多一天只能打S个怪物。如果力量P<a。这个勇士就回来。这天结束,每个勇士可以使用无数次。问最少需要多少天,能把所有的怪物全部打败。
思路:我们当然希望明天能够打的怪物越多越好。当前位置L,对于一个位置R(R>=L)要打败这个区间的所有怪物,就必须存在一个耐力>=R-L+1并且力量P>=max(a[L, R])的勇士。那么就是一个区间最大值查询,以X轴为力量建一棵线段树。
而R的位置我们可以二分。而且有一个怪物区间最大值查询,可以用RMQ。
我们发现其实每次查询勇士的力量的那个耐力区间是一个以耐力排序的后缀。维护后缀max以可以做。
#include<bits/stdc++.h>
#define LL long long
using namespace std;
int a[200005], b[200005], c[200005];
#define MAX_NODE 800005
#define MAX_ 200005
struct NODE
{
int l, r;
}node[MAX_NODE];
int f[MAX_]; //记录节点i的node结构体数组下标f[i]
int mx[MAX_NODE];//维护区间的值(最大值)
const int maxn=2e5+10;
int dp[maxn][31];
int dfs(int n)
{
for(int j=1;(1<<j)<=n;j++)
{
for(int i=1;i+(1<<j)-1<=n;i++)
{
dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);//dp的思想
}
}
}
int RMQ(int l, int r)
{
int k=log2(r-l+1); //k=小等于r-l+1区间长度 最大2的冪
return max(dp[l][k], dp[r-(1<<(k))+1][k]); //可能有重叠区间=只能维护最值, 维护和用前缀和
}
void BT(int i, int l ,int r) //建树
{
node[i].l=l;
node[i].r=r;
mx[i]=0;
if(l==r) //根节点
{
f[l]=i;
return;
}
BT((i<<1), l, (l+r)/2); //建左子树
BT((i<<1)+1, (l+r)/2+1, r);//建右子树
/***************/
mx[i]=max(mx[(i<<1)], mx[(i<<1)+1]);
/***************/
}
void UP(int i) //更新
{
if(i==1) //更新到根节点以上停止更新
{
return;
}
int p=i/2;
mx[p]=max(mx[(p<<1)], mx[(p<<1)+1]);
UP(p); //更新父节点
}
/*************/
int MAX=0; //记录每次的查询结果
/*************/
void FD(int i, int l, int r) //查找
{
if(node[i].l==l&&node[i].r==r)
{
/************/
MAX=max(MAX, mx[i]); //维护查询值
/************/
return;
}
int L=i<<1; //左子树
if(l<=node[L].r)
{
if(r<=node[L].r)
{
FD(L, l, r); //全部在左区间
}
else
{
FD(L, l, node[L].r);//部分在右区间
}
}
int R=(i<<1)+1;
if(r>=node[R].l)
{
if(l>=node[R].l) //全部在右区间
{
FD(R, l, r);
}
else
{
FD(R, node[R].l, r);//部分在左区间
}
}
}
int main()
{
int t;scanf("%d", &t);
while(t--){
int n, m;scanf("%d", &n);
for(int i=1; i<=n; i++){
scanf("%d", &a[i]);
dp[i][0]=a[i];
}
dfs(n);
scanf("%d", &m);
BT(1, 1, n);
for(int i=1; i<=m; i++){
scanf("%d%d", &b[i], &c[i]);
mx[f[c[i]]]=max(b[i], mx[f[c[i]]]);
UP(f[c[i]]);
}
int ks=1, ans=0;
while(ks<=n){
int L=ks, R=n, k=-1;
while(L<=R){
int mid=(L+R)/2;
int p=RMQ(ks, mid);
int t=mid-ks+1;
//cout<<t<<endl;
MAX=0;
FD(1, t, n);
if(MAX>=p){
k=mid;
L=mid+1;
}
else{
R=mid-1;
}
}
if(k==-1){
ans=-1;
break;
}
else{
ans++;
ks=k+1;
}
}
printf("%d\n", ans);
}
return 0;
}