【大模拟】CSP202012-3 带配额的文件系统

#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>
#include<bitset>
#include<queue>
#include<vector>
#include<cstdio>
#include<set>
#include<map>
#include<cmath>
#define ll long long

using namespace std;
const ll inf = 2e18;
struct node {
	ll type;//1 文件 2 目录
	map<string,ll>nt;
	ll ld,lr;//目录配额 后代配额
	ll size,d,r;//已用目录配额和后代配额
}z[2000005];

ll cnnt=1,rt=1;
string SS;//输入
vector<string>lj;//路径
vector<ll>ve;//一路下去搜的路
void getpath() {
	SS.push_back(‘/‘);
	ll sz = SS.size();
	ll L = 1; ll R=1;
	while(R<sz) {
		while(SS[R]!=‘/‘) R++;
		string tmps = SS.substr(L,R-L);
		lj.push_back(tmps);
		R++; L = R;
	}
}

ll NSZ;//创建的大小
bool crt(ll p,ll cs) { //结点 路径层数

	ll nxtp = z[p].nt[lj[cs]]; //下结点

	if(cs==lj.size()-1) { //创建层
		if(nxtp) {
			if(z[nxtp].type==2) return 0;
			if(z[nxtp].type==1) {
				ll desize = NSZ-z[nxtp].size;//改变额
				if(z[p].ld-z[p].d<desize) return 0;
				for(ll i=0;i<ve.size();i++) {
					if(z[ve[i]].lr-z[ve[i]].r<desize) return 0;
				}
				//成功新文件
				z[nxtp].size = NSZ;
				z[p].d += desize;
				for(ll i=0;i<ve.size();i++) {
					z[ve[i]].r += desize;
				}
				return 1;
			}  
		}
		ll desize = NSZ;
		if(z[p].ld-z[p].d<desize) return 0;
		for(ll i=0;i<ve.size();i++) {
			if(z[ve[i]].lr-z[ve[i]].r<desize) return 0;
		}
		//yes
		nxtp = ++cnnt;
		z[p].nt[lj[cs]] = nxtp;
		z[nxtp].size = NSZ;
		z[nxtp].type = 1;
		z[p].d += desize;
		for(ll i=0;i<ve.size();i++) {
			z[ve[i]].r += desize;
		}
		return 1;
		 //新文件
	}

	if(!nxtp) { //没有这个文件夹
		nxtp = ++cnnt;
		z[p].nt[lj[cs]] = nxtp;
		z[nxtp].ld = z[nxtp].lr = inf; z[nxtp].type = 2;
		ve.push_back(nxtp);
		bool fla = crt(nxtp,cs+1);
		if(!fla) {
			z[p].nt[lj[cs]] = 0;
			return 0;
		} //fail
		return 1;
	}
	if(z[nxtp].type==1) return 0;
	ve.push_back(nxtp);
	return crt(nxtp,cs+1);
}

void rmv(ll p,ll cs) {
	ll nxtp = z[p].nt[lj[cs]];
	if(!nxtp) return;
	if(cs==lj.size()-1) {
		ll desize = -(z[nxtp].size + z[nxtp].r);
		//若文件则size,若夹子则为后代用额。
		z[p].nt[lj[cs]] = 0;
		if(z[nxtp].type==1) z[p].d += desize;
		for(ll i=0;i<ve.size();i++) {
			z[ve[i]].r += desize;
		}
		return;
	}
	ve.push_back(nxtp);
	rmv(nxtp,cs+1);
}

bool QQ(ll p,ll cs,ll SZLD,ll SZLR) {
	ll nxtp = z[p].nt[lj[cs]];
	if(!nxtp) return 0;
	if(cs==lj.size()-1) {
		if(z[nxtp].type==1) return 0;
		if(z[nxtp].d>SZLD||z[nxtp].r>SZLR) return 0;
		z[nxtp].ld = SZLD; z[nxtp].lr = SZLR;
		return 1;
	}
	if(z[nxtp].type==1) return 0;
	return QQ(nxtp,cs+1,SZLD,SZLR);
}

char op[2];

int main(){
	z[rt].type=2; z[rt].lr=z[rt].ld=inf;
	z[rt].nt[""]=1;
	ll n;
	scanf("%lld",&n);
	while(n--) {
		scanf("%s",&op[1]);
		cin>>SS; lj.clear();
		getpath();
		if(op[1]==‘C‘) {
			scanf("%lld",&NSZ);
			ve.clear(); ve.push_back(rt);
			printf("%c\n",(crt(rt,0)?‘Y‘:‘N‘));
		} else if(op[1]==‘R‘) {
			ve.clear(); ve.push_back(rt);
			rmv(rt,0);
			puts("Y");
		} else if(op[1]==‘Q‘) {
			ll SZLD,SZLR;
			scanf("%lld%lld",&SZLD,&SZLR);
			if(SZLD==0) SZLD = inf;
			if(SZLR==0) SZLR = inf;
			printf("%c\n",(QQ(rt,0,SZLD,SZLR))?‘Y‘:‘N‘);
		}
	}
	return 0;
}