poj3667的加强版 当时的题解
这里只不过对于女神需要另开算，DS的占用的时间不加在女神身上，女神的时间都要加，清空的时候也都要算。
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
using namespace std;
#define N 100010
#define LL long long
#define INF 0xfffffff
const double eps = 1e-;
const double pi = acos(-1.0);
const double inf = ~0u>>;
int lm[N<<],ll[N<<],lr[N<<];
int nlm[N<<],nll[N<<],nlr[N<<];
int lz[N<<],nlz[N<<];
void up(int w,int m)
{
ll[w] = ll[w<<]==(m-m/)?ll[w<<|]+ll[w<<]:ll[w<<];
lr[w] = lr[w<<|]==(m/)?lr[w<<]+lr[w<<|]:lr[w<<|];
lm[w] = max(max(lm[w<<],lm[w<<|]),lr[w<<]+ll[w<<|]);
nll[w] = nll[w<<]==(m-m/)?nll[w<<|]+nll[w<<]:nll[w<<];
nlr[w] = nlr[w<<|]==(m/)?nlr[w<<]+nlr[w<<|]:nlr[w<<|];
nlm[w] = max(max(nlm[w<<],nlm[w<<|]),nlr[w<<]+nll[w<<|]);
}
void down(int w,int m)
{
if(lz[w]!=-)
{
ll[w<<] = lr[w<<] = lm[w<<] = lz[w]?(m-m/):;
ll[w<<|] = lr[w<<|] = lm[w<<|] = lz[w]?(m/):;
lz[w<<] = lz[w<<|] = lz[w];
lz[w] = -;
}
if(nlz[w]!=-)
{
nll[w<<] = nlr[w<<] = nlm[w<<] = nlz[w]?(m-m/):;
nll[w<<|] = nlr[w<<|] = nlm[w<<|] = nlz[w]?(m/):;
nlz[w<<] = nlz[w<<|] = nlz[w];
nlz[w] = -;
}
}
void build(int l,int r,int w)
{
if(l==r)
{
lm[w] = ll[w] = lr[w] = ;
nlm[w] = nll[w] = nlr[w] = ;
return ;
}
int m = (l+r)>>;
build(l,m,w<<);
build(m+,r,w<<|);
up(w,r-l+);
}
void update(int a,int b,int d,int flag,int l,int r,int w)
{
if(a<=l&&b>=r)
{
if(flag)
{
nlm[w] = nll[w] = nlr[w] = d*(r-l+);
nlz[w] = d;
}
lm[w] = ll[w] = lr[w] = d*(r-l+);
lz[w] = d;
return ;
}
down(w,r-l+);
int m = (l+r)>>;
if(a<=m)
update(a,b,d,flag,l,m,w<<);
if(b>m)
update(a,b,d,flag,m+,r,w<<|);
up(w,r-l+);
}
int find(int k,int f,int l,int r,int w)
{
if(l==r)
{
return l;
}
int m = (l+r)>>;
down(w,r-l+);
if(f)
{
if(lm[w<<]>=k)
return find(k,f,l,m,w<<);
else if(lr[w<<]+ll[w<<|]>=k)
return m-lr[w<<]+;
else return find(k,f,m+,r,w<<|);
}
else
{
if(nlm[w<<]>=k)
return find(k,f,l,m,w<<);
else if(nlr[w<<]+nll[w<<|]>=k)
return m-nlr[w<<]+;
else return find(k,f,m+,r,w<<|);
}
}
int main()
{
int n,kk=,t,q;
int x,y;
char s[];
scanf("%d",&t);
while(t--)
{
memset(lz,-,sizeof(lz));
memset(nlz,-,sizeof(nlz));
scanf("%d%d",&n,&q);
build(,n,);
printf("Case %d:\n",++kk);
while(q--)
{
scanf("%s%d",s,&x);
if(s[]=='D')
{
if(lm[]<x)
puts("fly with yourself");
else
{
int k = find(x,,,n,);
update(k,k+x-,,,,n,);
printf("%d,let's fly\n",k);
}
}
else if(s[]=='N')
{
if(lm[]>=x)
{
int k = find(x,,,n,);
printf("%d,don't put my gezi\n",k);
update(k,k+x-,,,,n,);
}
else if(nlm[]>=x)
{
int k = find(x,,,n,);
printf("%d,don't put my gezi\n",k);
update(k,k+x-,,,,n,);
}
else puts("wait for me");
}
else
{
scanf("%d",&y);
update(x,y,,,,n,);
printf("I am the hope of chinese chengxuyuan!!\n");
}
}
}
return ;
}