免费建网站哪个平台好,php 未定义函数wordpress,邢台公共服务平台官网,网页游戏排行榜前十名2021约会安排 HDU - 4553
题意#xff1a; 题意又丑又长就不叙述了
题解#xff1a;
这个题一开始理解错了。。。题目相当于是有三种情况占据时间#xff0c;分别是学习#xff0c;女神和屌丝#xff0c;我们用不同的lazy来表示女神和屌丝#xff0c;根据优先级去更新状态…约会安排 HDU - 4553
题意 题意又丑又长就不叙述了
题解
这个题一开始理解错了。。。题目相当于是有三种情况占据时间分别是学习女神和屌丝我们用不同的lazy来表示女神和屌丝根据优先级去更新状态。 学习pushdown时会讲女神和屌丝的lazy清空女神会把屌丝的清空。相同类型所占区间要进行合并。但是要注意学习时间可以被后面任意 在为屌丝安排时顺序安排时间 为女神安排时先看屌丝是否有空余时间如果没有直接无视屌丝(因为可以占用屌丝时间)直接判断女神时间是否有连续x长的空余时间 lsrsms分别表示左/右和整个区间最长连续空时间的长度 这个题是不错的多lazy区间合并的好题目
代码
#include stdio.h
#include string.h
#include algorithm
using namespace std;const int L 100000 10;struct node
{int lazydiaosi, lazynvshen, lazystudy;int ls, rs, ms; //屌丝标记int nsl, nsr, nsm; //女神标记
} a[L 2];void diaosi(int l, int r, int i)
{a[i].lazydiaosi 1;a[i].ls a[i].rs a[i].ms 0;
}void nvshen(int l, int r, int i)
{a[i].lazynvshen 1;a[i].lazydiaosi 0;a[i].ls a[i].rs a[i].ms 0;a[i].nsl a[i].nsr a[i].nsm 0;
}void xuexi(int l, int r, int i)
{a[i].lazystudy 1;a[i].lazydiaosi a[i].lazynvshen 0;//屌丝女神标记清空a[i].ls a[i].rs a[i].ms r - l 1;a[i].nsl a[i].nsr a[i].nsm r - l 1;
}void pushup(int l, int r, int i)//区间合并
{int mid (l r) 1;a[i].ms max(a[2 * i].ms, a[2 * i 1].ms);a[i].ms max(a[i].ms, a[2 * i].rs a[2 * i 1].ls);a[i].ls a[2 * i].ls;a[i].rs a[2 * i 1].rs;if (a[2 * i].ls mid - l 1)a[i].ls a[2 * i 1].ls;if (a[2 * i 1].rs r - mid)a[i].rs a[2 * i].rs;a[i].nsm max(a[2 * i].nsm, a[2 * i 1].nsm);a[i].nsm max(a[i].nsm, a[2 * i].nsr a[2 * i 1].nsl);a[i].nsl a[2 * i].nsl;a[i].nsr a[2 * i 1].nsr;if (a[2 * i].nsl mid - l 1)a[i].nsl a[2 * i 1].nsl;if (a[2 * i 1].nsr r - mid)a[i].nsr a[2 * i].nsr;
}void pushdown(int l, int r, int i)
{int mid (l r) 1;//按照优先级依次下降lazyif (a[i].lazystudy) {xuexi(l, mid, 2 * i);xuexi(mid 1, r, 2 * i 1);a[i].lazystudy 0;}if (a[i].lazydiaosi) {diaosi(l, mid, 2 * i);diaosi(mid 1, r, 2 * i 1);a[i].lazydiaosi 0;}if (a[i].lazynvshen) {nvshen(l, mid, 2 * i);nvshen(mid 1, r, 2 * i 1);a[i].lazynvshen 0;}
}void study(int L, int R, int l, int r, int i)
{if (L l R r) {xuexi(l, r, i);return;}int mid (l r) 1;pushdown(l, r, i);if (R mid)study(L, R, l, mid, 2 * i);else if (L mid)study(L, R, mid 1, r, 2 * i 1);else {study(L, mid, l, mid, 2 * i);study(mid 1, R, mid 1, r, 2 * i 1);}pushup(l, r, i);
}void insert(int flag, int L, int R, int l, int r, int i)
{if (l L r R) {if (!flag)diaosi(l, r, i);elsenvshen(l, r, i);return;}int mid (l r) 1;pushdown(l, r, i);if (R mid)insert(flag, L, R, l, mid, 2 * i);else if (L mid)insert(flag, L, R, mid 1, r, 2 * i 1);else {insert(flag, L, mid, l, mid, 2 * i);insert(flag, mid 1, R, mid 1, r, 2 * i 1);}pushup(l, r, i);
}int query(int flag, int t, int l, int r, int i)
{if (l r)return l;int mid (l r) 1;pushdown(l, r, i);if (!flag) {//屌丝if (a[2 * i].ms t)//左子树有时间return query(flag, t, l, mid, 2 * i);else if (a[2 * i].rs a[2 * i 1].ls t)//右子树右子树有时间return mid - a[2 * i].rs 1;else//右子树有时间return query(flag, t, mid 1, r, 2 * i 1);}else {if (a[2 * i].nsm t)return query(flag, t, l, mid, 2 * i);else if (a[2 * i].nsr a[2 * i 1].nsl t)return mid - a[2 * i].nsr 1;elsereturn query(flag, t, mid 1, r, 2 * i 1);}
}int main()
{int t, i, x, y, ans, cas 1, n, m;char str[20];scanf(%d, t);while (t--) {scanf(%d%d, n, m);printf(Case %d:\n, cas);study(1, n, 1, n, 1);while (m--) {scanf(%s, str);if (str[0] D) {scanf(%d, x);if (a[1].ms x) //线段树最大的区间都小于给定的时间就不用找了printf(fly with yourself\n);else {ans query(0, x, 1, n, 1);insert(0, ans, ans x - 1, 1, n, 1);printf(%d,lets fly\n, ans);}}else if (str[0] N) {scanf(%d, x);if (a[1].ms x) {if (a[1].nsm x)printf(wait for me\n);else {ans query(1, x, 1, n, 1);insert(1, ans, ans x - 1, 1, n, 1);printf(%d,dont put my gezi\n, ans);}}else {ans query(0, x, 1, n, 1);insert(1, ans, ans x - 1, 1, n, 1);printf(%d,dont put my gezi\n, ans);}}else {scanf(%d%d, x, y);study(x, y, 1, n, 1);printf(I am the hope of chinese chengxuyuan!!\n);}}}return 0;
}
