put my gezi这句话不得不说我看了好几秒才反应过来什么意思(你咋不上天呢
目测了一下也是区间合并 但是是成段更新的区间合并 但是!我终于!自己!写出来了!
嗯还算是比较顺利的 query的地方想了想也写出来了 就是lazy标记我竟然一时忘了怎么打(犯蠢了 后来想起来默认打上-1就行了
#include <cstdio> #include <cmath> #include <cstring> #include <stack> #include <algorithm> #define INF 0x3f3f3f3f #define mem(str,x) memset(str,(x),sizeof(str)) #define STOP puts("Pause"); #define lson l, m, rt<<1 #define rson m+1, r, rt<<1|1 using namespace std; typedef long long LL; const int MAXN = 100005; int n, m; int dsll[MAXN<<2], dsrl[MAXN<<2], dsml[MAXN<<2], dslazy[MAXN<<2]; int nsll[MAXN<<2], nsrl[MAXN<<2], nsml[MAXN<<2], nslazy[MAXN<<2]; inline void dspushdown(int l, int r, int rt){ if(~dslazy[rt]){ int m = (l + r) >> 1; //printf("pushdown %d to %d ", l, r); dslazy[rt<<1] = dslazy[rt<<1|1] = dslazy[rt]; dsll[rt<<1] = dsrl[rt<<1] = dsml[rt<<1] = (m - l + 1) * dslazy[rt]; dsll[rt<<1|1] = dsrl[rt<<1|1] = dsml[rt<<1|1] = (r - m) * dslazy[rt]; dslazy[rt] = -1; } } inline void nspushdown(int l, int r, int rt){ if(~nslazy[rt]){ int m = (l + r) >> 1; nslazy[rt<<1] = nslazy[rt<<1|1] = nslazy[rt]; nsll[rt<<1] = nsrl[rt<<1] = nsml[rt<<1] = (m - l + 1) * nslazy[rt]; nsll[rt<<1|1] = nsrl[rt<<1|1] = nsml[rt<<1|1] = (r - m) * nslazy[rt]; nslazy[rt] = -1; } } void build(int l, int r, int rt) { dslazy[rt] = nslazy[rt] = -1; dsll[rt] = dsrl[rt] = dsml[rt] = r - l + 1; nsll[rt] = nsrl[rt] = nsml[rt] = r - l + 1; if(l == r) return; int m = (l + r) >> 1; build(lson); build(rson); } void dsupdate(int L, int R, int c, int l, int r, int rt) { if(l >= L && r <= R){ dslazy[rt] = c; dsll[rt] = dsrl[rt] = dsml[rt] = (r - l + 1) * c; //printf("update ds from %d to %d into 0 ", l, r); return; } dspushdown(l, r, rt); int m = (l + r) >> 1; if(L <= m) dsupdate(L, R, c, lson); if(R > m) dsupdate(L, R, c, rson); if((dsll[rt] = dsll[rt<<1]) == m - l + 1) dsll[rt] += dsll[rt<<1|1]; if((dsrl[rt] = dsrl[rt<<1|1]) == r - m) dsrl[rt] += dsrl[rt<<1]; dsml[rt] = max(max(dsml[rt<<1], dsml[rt<<1|1]), dsrl[rt<<1] + dsll[rt<<1|1]); } void nsupdate(int L, int R, int c, int l, int r, int rt) { if(l >= L && r <= R){ nslazy[rt] = c; nsll[rt] = nsrl[rt] = nsml[rt] = (r - l + 1) * c; return; } nspushdown(l, r, rt); int m = (l + r) >> 1; if(L <= m) nsupdate(L, R, c, lson); if(R > m) nsupdate(L, R, c, rson); if((nsll[rt] = nsll[rt<<1]) == m - l + 1) nsll[rt] += nsll[rt<<1|1]; if((nsrl[rt] = nsrl[rt<<1|1]) == r - m) nsrl[rt] += nsrl[rt<<1]; nsml[rt] = max(max(nsml[rt<<1], nsml[rt<<1|1]), nsrl[rt<<1] + nsll[rt<<1|1]); } //查询len长度的时间段起点 不存在则返回0 int dsquery(int len, int l, int r, int rt) { //printf("check %d to %d ll = %d rl = %d ml = %d ", l, r, dsll[rt], dsrl[rt], dsml[rt]); if(len > dsml[rt]) return 0; int m = (l + r) >> 1; if(len <= dsll[rt]) return l; if(len <= dsml[rt<<1]) return dsquery(len, lson); else if(len <= dsrl[rt<<1] + dsll[rt<<1|1]) return m + 1- dsrl[rt<<1]; else return dsquery(len, rson); } int nsquery(int len, int l, int r, int rt) { if(len > nsml[rt]) return 0; int m = (l + r) >> 1; if(len <= nsll[rt]) return l; if(len <= nsml[rt<<1]) return nsquery(len, lson); else if(len <= nsrl[rt<<1] + nsll[rt<<1|1]) return m + 1- nsrl[rt<<1]; else return nsquery(len, rson); } int main() { int t; scanf("%d", &t); for(int kase = 1; kase <= t; kase++){ int x, y, len; char order[10]; scanf("%d%d", &n, &m); build(1, n, 1); printf("Case %d: ", kase); while(m--){ scanf("%s", order); if(order[0] == 'D'){ scanf("%d", &len); x = dsquery(len, 1, n, 1); if(x){ y = x + len - 1; dsupdate(x, y, 0, 1, n, 1); printf("%d,let's fly ", x); } else puts("fly with yourself"); } else if(order[0] == 'N'){ scanf("%d", &len); x = dsquery(len, 1, n, 1); if(x){ y = x + len - 1; dsupdate(x, y, 0, 1, n, 1); nsupdate(x, y, 0, 1, n, 1); printf("%d,don't put my gezi ", x); } else{ x = nsquery(len, 1, n, 1); if(x){ y = x + len - 1; dsupdate(x, y, 0, 1, n, 1); nsupdate(x, y, 0, 1, n, 1); printf("%d,don't put my gezi ", x); } else puts("wait for me"); } } else{ scanf("%d%d", &x, &y); dsupdate(x, y, 1, 1, n, 1); nsupdate(x, y, 1, 1, n, 1); puts("I am the hope of chinese chengxuyuan!!"); } } } return 0; }