找区间内第一个比x小(大)的数(线段树/单调栈)(ACM-ICPC 2018 南京赛区网络预赛 B G题解)
ACM/ICPC 2018 南京网络预赛 G Lpl and Energy-saving Lamps
题意:
共有n间房间，在每间房间里有k[i]排台灯。你将全部房间的所有盏台灯更换为新型节能型灯具。
你在每个月一开始会买m栈节能台灯。
更换台灯的规则是从可更换区域的第一个房间开始执行；当遇到一个房间时，则按照以下条件进行判断：若该房间配备的第一盏节能台灯尚未达到使用上限，则立即开启；否则，在保证现有能源使用效率的前提下逐步增加新的节能照明设备；最终将所有剩余未使用的节能照明设备依次分配至其他符合条件且能有效减少能源浪费的位置进行安装或维护工作
那么就可以将他替换出去，并将其从列表中删除。否则则跳过该房间，并进入下一个房间。
当你的节能台灯库存耗尽或者完成全部房间的遍历时，本月的任务即告结束。
你剩下的节能台灯在下个月还能正常使用。到了某个月月底时,如果每个房间都已经更换了灯具,那么你就不会再再去购买新的灯具了.
节能台灯了
q个查询项，在每一个di月结束后进行查询，在第di个月末的情况中，请问您更换了多少间房间？剩余了多少盏节能灯？
n<=1e5,m<=100,di<=1e5,ki<=1e4,q<=1e5
解析:
这里我是直接正面求解，模拟每一次换台灯的过程。
完成更换第j个房间后，在区间[j+1, n]中寻找第一个节能台灯数量少于当前值money的房间。
接着我采用线段树来进行模拟。为了提高效率，在查询过程中适当加入剪枝策略（否则时间复杂度可能过高）。
因为每一个房间只会被删除一次，那么时间复杂度接近为O(nlogn)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
#define Min(a,b) a>=b?b:a;
#define Max(a,b) a>=b?a:b;
const int MAXN = 1e5+100;
const int INF = 0x3f3f3f3f;
int b[MAXN];
char str[10];
#define lch root<<1
#define rch (root<<1)|1
typedef long long ll;
typedef struct node
{
int ans;
int minn;
int pos;
}node;
node Btree[MAXN*5];
int res[MAXN][2];
inline void push_up(int root)
{
/*if(Btree[lch].minn>Btree[rch].minn)
{
Btree[root].minn=Btree[rch].minn;
Btree[root].pos=2;
}
else if(Btree[lch].minn<Btree[rch].minn)
{
Btree[root].minn=Btree[lch].minn;
Btree[root].pos=1;
}
else
{
Btree[root].minn=Btree[lch].minn;
Btree[root].pos=3;
}*/
Btree[root].minn=Min(Btree[lch].minn,Btree[rch].minn);
}
void build(int l,int r,int root) //l,r表示他们在stu中的下标,root表示他们在线段树中的坐标
{
if(l>r)return;
if(l==r)
{
Btree[root].ans=l; //下标
//Btree[root].pos=0;
Btree[root].minn=b[l];
return ;
}
int mid=(l+r)>>1;
build(l,mid,root<<1);
build(mid+1,r,(root<<1)|1);
push_up(root);
}
void updateone(int root,int s1,int e1,int ind) //将b[ind]置为INF，即将b[ind]删除
{
if(s1>e1)return;
if(s1==e1&&s1==ind)
{
Btree[root].minn=INF;
return;
}
//pushDown(root);
int mid=(s1+e1)>>1;
if(ind<=mid)
updateone(root<<1,s1,mid,ind);
else
updateone((root<<1)|1,mid+1,e1,ind);
push_up(root);
}
int query(int root,int s1,int e1,int l,int r,int val) //查询[l,r]内第一个小于val的数的下标，从左往右
{
if(s1>e1)return 0;
if(s1==e1)
{
return Btree[root].minn<=val?Btree[root].ans:0;
}
//pushDown(root);
int mid=(s1+e1)>>1;
int pl,pr;
pl=pr=0;
if(l<=s1&&e1<=r&&Btree[root].minn<=val)
{
if(Btree[lch].minn<=val) //左边有最小值小于val
return query(root<<1,s1,mid,l,r,val);
else
return query((root<<1)|1,mid+1,e1,l,r,val);
}
else
{
if(l<=mid&&Btree[lch].minn<=val) pl=query(root<<1,s1,mid,l,r,val);
if(pl) return pl; //左边有最小值小于val
if(r>mid&&Btree[rch].minn<=val) pr=query((root<<1)|1,mid+1,e1,l,r,val);
return pr;
}
return 0;
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&b[i]);
build(1,n,1);
int money=m;
int tmp=0;
int i;
for(i=1;i<=100000&&tmp<n;i++)
{
int kk=query(1,1,n,1,n,money);
while(kk)
{
tmp++;
money-=b[kk];
b[kk]=INF;
updateone(1,1,n,kk);
if(kk>=n) break;
kk=query(1,1,n,kk+1,n,money);
}
res[i][0]=tmp;
res[i][1]=money;
money+=m;
//if(tmp>=n) break;
}
int q,y;
scanf("%d",&q);
for(int j=0;j<q;j++)
{
scanf("%d",&y);
y=Min(i-1,y);
printf("%d %d\n",res[y][0],res[y][1]);
}
return 0;
}ACM-ICPC 2018 南京赛区网络预赛 B. The writing on the wall (单调栈+dp)
题意:
给你一个nm的方格，里面都是由nm个1*1的小方格构成的
然后其中有k个点是被挖空的，输入下面k行，每行x,y表示被挖空的点(1<=x<=n,1<=y<=m)
最后问你能里面有多少个矩形？
没有被挖过的是有36个矩形
中间被挖掉一个，只有20个矩形
1<=n<=1e5,1<=m<=100,1<=k<=1e5
解析:
用dp维护
dp[i][j]表示i*j大小的矩阵有多少个矩形
那么
dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+qsum[i]
qsum[i]代表包含(i,j)这一格所形成的矩形数量，并且新增加的部分同样计入其中
随后的主要任务就是计算qsum[i]。最初尝试使用树状数组进行求解,但这种方法在实际应用中存在明显局限性,导致比赛最终失利
后来想了一下，发现可以用单调队列+前缀数组解决.....
先用一个yang[w]，表示对第w行中，被挖空的方格到当前列j的距离
例如对于上面挖空的矩阵样例，i=3,j=3,yang[1]=3,yang[2]=1,yang[1]=3
那么我们可以发现，其实对于i=3,j=3,第一行只能贡献+1的答案，但是yang[1]=3
然后我们就需要用一个monotonic queue/monotonic stack来进行处理（其中我们采用的是一个monotonic queue来处理问题），具体来说，在处理第二行时
然后这之间的行对答案的贡献都是yang[2],其实就是下图
对于(i,j)，每一行的贡献就是绿色部分。
那么我们依次逐行处理每一行，并将其加入到单调队列中。为了确保队列始终是最小值优先排列的结构，在此过程中会移除所有位于当前行之前的且数值较大的元素。
接着根据比当前行id小的第一个行, 建立一个前缀数组用于临时存储 qsum[i] = yang[i] * (i - id) + qsum[i].
最后输出dp[n][m]就可以了。
利用单调栈，可以找到从左/右遍历第一个比它小/大的元素的位置
这个问题涉及在填充时将dp[i][j]用来表示一个j乘i维度的矩阵。其中n和m尺寸不一致导致数组配置错误。这使得小规模数据能够正确处理但大规模数据却可能出现错误
改了一个下午，以为是答案超long long，结果用公式推出来k=0时ans=(1+n)n(1+m)*m/4
根本不会爆long long 。。。。最后发现了错误，真的是不好的代码习惯....
#include <cstdio>
#include <cstring>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<ll,int> pII;
const int MAXN = 1e5+10;
const int MAXM = 100+1;
const ll INF = 0x3f3f3f3f3f3f3f3f;
typedef struct node
{
ll x;
int id;
friend bool operator <(node a,node b)
{
return a.x<b.x;
}
}node;
int n,m,k;
int mp[MAXN][MAXM];
ll dp[MAXN][MAXM];
ll yang[MAXN];
node mq[MAXN];
ll qsum[MAXN];
int main()
{
int t;
scanf("%d",&t);
int cas=0;
while(t--)
{
cas++;
scanf("%d%d%d",&n,&m,&k);
for(int i=0;i<=n;i++)
{
for(int j=0;j<=m;j++)
mp[i][j]=1,dp[i][j]=0;
yang[i]=0;
}
for(int i=1;i<=k;i++)
{
int x,y;
scanf("%d%d",&x,&y);
mp[x][y]=0;
}
int beg;
int head,tail;
for(int i=1;i<=m;i++)
{
beg=0;
head=tail=0;
for(int j=1;j<=n;j++)
{
if(mp[j][i])
{
yang[j]++;
}
else
{
beg=j;
yang[j]=0;
}
dp[j][i]+=dp[j-1][i]+dp[j][i-1]-dp[j-1][i-1];
while (head<tail&&mq[tail-1].x>yang[j]) tail--;
if(head==tail) qsum[j]=yang[j]*j;
else qsum[j]=yang[j]*(j-mq[tail-1].id)+qsum[mq[tail-1].id];
mq[tail++]=node{yang[j],j};
dp[j][i]+=qsum[j];
}
}
printf("Case #%d: %lld\n",cas,dp[n][m]);
}
return 0;
}