这个牛半仙可真的是人生赢家

这波中二的名字又是让我心头一震，然后有发现没有 \(PDF\) 和大样例。

没有大样例就意味着不能打挂一处。

然而这是让我最头疼的事情。。。

\(100\) 多行的代码一般对我来说也就是不到 \(5\) 分钟就能打完，然后开始 \(50min\) 调试。。。

有亿点亏。。。

其实这样的联赛模拟题目使劲想一想还是可以想出正解的，然而脑袋里不知道为什么总是想要去打一个暴力。。。

确实该改一改这个毛病。

牛半仙的妹子图

一开始看这个题目的时候就觉得这个出题人真的是中二至极。

这就是我打挂这个题目的理由

这个题目实际上很像奶牛跨栏那个题目，就是要求到达一个点路径上的最小值的最大。

然而当时所有人似乎用的都是 \(floyed\) 高级算法。。。

然后这个题目就不知道用 \(dij\) 咋搞。。。

其实也差不多，我想的是可以把所有边压进 ￥priority_queue$ 当中，这样的话也能维护这个。

然而因为不是很经常使用 \(dijkstra\) 和 \(priority_queue\)，所以。。。

我压根不知道该 反着重载。

所以我是这么写的。。。

class xin_data
{
	private:
		friend bool operator < (xin_data x,xin_data y)
		{return x.w < y.w;}
	public:
		int w,pos;
};

然后就 \(gg\) 了。

因为 \(w\leq600\) ，所以可以建立 权值数组。

然后就能跑了。

#include<bits/stdc++.h>
using std::cout; using std::endl;
#define try(i,a,b) for(register signed i=a;i<=b;++i)
#define throw(i,a,b) for(register signed i=a;i>=b;--i)
#define int long long
namespace xin_io
{
	#define scanf nb = scanf
	#define debug cout<<"debug"<<endl
	#define gc() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<2,stdin),p1 == p2) ? EOF : *p1++
	char buf[1<<20],*p1 = buf,*p2 = buf,output[100]; FILE *xinnb;int nb;typedef long long ll; typedef unsigned long long ull;
	void openfile() {xinnb = freopen("t.txt","r",stdin);} void outfile() {xinnb = freopen("o.txt","w",stdout);}
	inline int get()
	{
		register int s = 0,f = 1; register char ch = gc();	while(!isdigit(ch)) {if(ch == '-') f = -1; ch = gc();}
		while( isdigit(ch)) s = (s << 1) + (s << 3) + (ch xor 48),ch = gc();return s * f;
	}
	template<typename type>inline void write(type x,char out)
	{
		if(!x) return putchar('0'),putchar(out),void(); if(x < 0) putchar('-'),x = -x;
		register int cnt = 0;while(x) output[++cnt] = x % 10,x /= 10; 
		throw(i,cnt,1) putchar(output[i] xor 48);return putchar(out),void();
	}
}
using namespace xin_io; static const int maxn = 1e6+10,inf = 1e9+7; static const ll llinf = 1e17+7;
namespace xin
{
	class xin_edge{public:int next,ver,w;}edge[maxn];
	int head[maxn],zhi = 0;
	inline void add(int x,int y,int z) {edge[++zhi].ver = y;edge[zhi].w = z; edge[zhi].next = head[x]; head[x] = zhi;}
	class xin_data
	{
		private:
			friend bool operator < (xin_data x,xin_data y)
			{return x.val > y.val;}
		public:
			int val,pos;
			xin_data(){}
			xin_data(int val,int pos):val(val),pos(pos){}
	};
	std::priority_queue<xin_data>q;
	int n,m,qnum,st,op,mod,c[maxn],dis[maxn];
	int ton[maxn],sum = 0;
	int he[maxn],base[maxn],cnt,num[maxn];
	bool vis[maxn];
	inline short main()
	{
	#ifndef ONLINE_JUDGE
		openfile();
	#endif
		n = get(); m = get(); qnum = get(); st = get(); op = get(); if(op) mod = get();
		try(i,1,n) c[i] = get();
		try(i,1,m)
		{
			register int x = get(),y = get(),z = get();
			add(x,y,z); add(y,x,z);
		}
		ton[c[st]]++; sum ++;
		for(register int i=head[st];i;i=edge[i].next) q.push(xin_data(edge[i].w,edge[i].ver));
		int maxx = 0; base[++cnt] = 1; num[cnt] = sum;
		while(!q.empty())
		{
			register int dis = q.top().val,now = q.top().pos;q.pop();
			if(vis[now])continue;
			vis[now] = 1; maxx = std::max(maxx,dis);
			ton[c[now]]++; if(ton[c[now]] == 1) {sum++; if(base[cnt] xor maxx) base[++cnt] = maxx; num[cnt] = sum;}
			for(register int i=head[now];i;i=edge[i].next) q.push(xin_data(edge[i].w,edge[i].ver));
		}
		base[++cnt] = inf;
		try(i,1,cnt) he[i] = he[i-1] + num[i - 1] * (base[i] - base[i-1]);
		int pre = 0;
		try(i,1,qnum)
		{
			register int l = get(),r = get();
			if(op) l = (l xor pre) % mod + 1,r = (r xor pre) % mod + 1;
			if(r < l) std::swap(l,r);
			register int lb = std::upper_bound(base+1,base+cnt+1,l) - base,rb = std::upper_bound(base+1,base+cnt+1,r) - base - 1;
			register int ans = he[rb] - he[lb];
			ans += (base[lb] - l) * num[lb - 1]; ans += (r - base[rb] + 1) * num[rb];
			write(pre = ans,'\n');
		}
		return 0;
	}
}
signed main(){return xin::main();}

牛半仙的妹子Tree

这个题目说实话我是真的没有想到暴力直接可过的。

然后加强数据之后。。。还是能过。。。

其实就是记录下来每一个 \(1\) 操作。

然后在每一个 \(3\) 操作的时候遍历整个 \(1\) 操作的数组。

然后而操作就是把那个数组的指针清零就行了。

然而 \(lca\) 一定要 \(\mathcal O(1)\) 求，不然一定会 \(T\)。

#include<bits/stdc++.h>
using std::cout; using std::endl;
#define try(i,a,b) for(register signed i=a;i<=b;++i)
#define throw(i,a,b) for(register signed i=a;i>=b;--i)
namespace xin_io
{
	#define scanf nb = scanf
	#define debug cout<<"debug"<<endl
	#define gc() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<2,stdin),p1 == p2) ? EOF : *p1++
	char buf[1<<20],*p1 = buf,*p2 = buf,output[100]; FILE *xinnb;int nb;typedef long long ll; typedef unsigned long long ull;
	void openfile() {xinnb = freopen("t.txt","r",stdin);} void outfile() {xinnb = freopen("o.txt","w",stdout);}
	inline int get()
	{
		register int s = 0,f = 1; register char ch = gc();	while(!isdigit(ch)) {if(ch == '-') f = -1; ch = gc();}
		while( isdigit(ch)) s = (s << 1) + (s << 3) + (ch xor 48),ch = gc();return s * f;
	}
	template<typename type>inline void write(type x,char out)
	{
		if(!x) return putchar('0'),putchar(out),void(); if(x < 0) putchar('-'),x = -x;
		register int cnt = 0;while(x) output[++cnt] = x % 10,x /= 10; 
		throw(i,cnt,1) putchar(output[i] xor 48);return putchar(out),void();
	}
}
using namespace xin_io; static const int maxn = 1e6+10,inf = 1e9+7; static const ll llinf = 1e17+7;
namespace xin
{
	class xin_edge{public:int next,ver;} edge[maxn];
	int head[maxn],cnt = 0;
	inline void add(int x,int y){edge[++cnt].ver = y; edge[cnt].next = head[x]; head[x] = cnt;}
	int dep[maxn],f[maxn][32],lg[maxn],fr[maxn],num;
	void dfs(int x,int fa)
	{
		dep[x]=dep[fa]+1;
		f[++num][0] = x;
		if(!fr[x])fr[x]=num;
		for(int i=head[x];i;i=edge[i].next)
		{
			int dd=edge[i].ver;
			if(dd==fa)continue;
			dfs(dd,x);
			f[++num][0]=x;
			if(!fr[x])fr[x]=num;
		}
	}
	void RMQ()
	{
		for(register int j=1;(1<<j)<=num;++j)
			for(register int i=1;i+(1<<j)-1<=num;++i)
				if(dep[f[i][j-1]]<dep[f[i+(1<<(j-1))][j-1]])f[i][j]=f[i][j-1];
				else f[i][j]=f[i+(1<<(j-1))][j-1];
		try(i,2,num) lg[i] = lg[i>>1] + 1;
	}

	int lca(int x,int y)
	{
		x = fr[x]; y = fr[y];
		if(x > y) x ^= y ^= x ^= y;
		int len=lg[y-x+1];
		return dep[f[x][len]]<dep[f[y-(1<<len)+1][len]]?f[x][len]:f[y-(1<<len)+1][len];
	}
	inline int distance(int x,int y){return dep[x] + dep[y] - 2 * dep[lca(x,y)];}
	int a[maxn],temp[maxn],zhi = 0;
	int n,m;
	bool cold[maxn];
	void kuosan()
	{
		try(i,1,zhi) temp[i] = a[i];
		int ms = zhi; zhi = 0;
		try(i,1,ms)
		{
			register int x = temp[i];
			for(register int i=head[x];i;i=edge[i].next)
			{
				register int y = edge[i].ver;
				if(!cold[y]) cold[y] = 1,a[++zhi] = y;
			}
		}
	}
	class xin_data
	{
		public:
			int tim,pos;
			xin_data(){}
			xin_data(int tim,int pos):tim(tim),pos(pos){}
	}d[maxn];
	bool sp1 = 1,sp2 = 1;
	inline short main()
	{
	#ifndef ONLINE_JUDGE
		openfile();
	#endif
		n = get(); m = get();
		try(i,1,n-1)
		{
			register int x = get(),y = get();
			add(x,y); add(y,x);
			if(x xor 1) sp1 = 0;
			if((x xor i) or (y xor (i + 1))) sp2 = 0;						
		}
		if(sp1)
		{
			int tim = 0,cnt = 0;
			try(i,1,m)
			{
				register int op = get(),x = get();
				if(cnt)
				{
					if(cold[1]) cnt = n;
					else cold[1] = 1;
				}
				if(op == 1)
				{
					cold[x] = 1;
					cnt++;
				}
				if(op == 2)
				{
					cnt = 0;
					memset(cold,0,sizeof(bool) * (n + 1));
				}
				if(op == 3)
				{
					if(cnt == n) printf("wrxcsd\n");
					else printf(cold[x] ? "wrxcsd\n" : "orzFsYo\n");	
				}
			}
			return 0;
		}	
		if(sp2)
		{
			try(i,1,m)
			{
				register int op = get(),x = get();
				kuosan();
				if(op == 1)
				{
					a[++zhi] = x;
					cold[x] = true;
				}
				if(op == 2)
				{
					memset(cold,0,sizeof(bool) * (n + 1));
					zhi = 0;
				}
				if(op == 3)
					printf(cold[x] ? "wrxcsd\n" : "orzFsYo\n");	
			}
			return 0;
		}
		dfs(1,0); RMQ();
		try(tim,1,m)
		{
			register int op = get(),x = get();
			if(op == 1)
			{
				d[++zhi] = xin_data(tim,x);
			}
			if(op == 2)
			{
				zhi = 0;
			}
			if(op == 3)
			{
				bool ok = 1;
				try(i,1,zhi)
				{
					register int ks = tim - d[i].tim,dis = distance(x,d[i].pos);
					if(ks >= dis) {ok = 0;break;}
				}
				puts(ok ? "orzFsYo" : "wrxcsd");
			}
		}
		return 0;
	}
}
signed main(){return xin::main();}

牛半仙的妹子序列

似乎是极长上升子序列的板子。

然而我不会。。。

然后 \(gg\) 了，直接这个题目抱 \(\color{red}{0}\) 了。

用线段树维护这个玩意，似乎和昨天的第二题有些相似。

#include<bits/stdc++.h>
using std::cout; using std::endl;
#define try(i,a,b) for(register signed i=a;i<=b;++i)
#define throw(i,a,b) for(register signed i=a;i>=b;--i)
namespace xin_io
{
	#define scanf nb = scanf
	#define debug cout<<"debug"<<endl
	#define gc() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<2,stdin),p1 == p2) ? EOF : *p1++
	char buf[1<<20],*p1 = buf,*p2 = buf,output[100]; FILE *xinnb;int nb;typedef long long ll; typedef unsigned long long ull;
	void openfile() {xinnb = freopen("t.txt","r",stdin);} void outfile() {xinnb = freopen("o.txt","w",stdout);}
	inline int get()
	{
		register int s = 0,f = 1; register char ch = gc();	while(!isdigit(ch)) {if(ch == '-') f = -1; ch = gc();}
		while( isdigit(ch)) s = (s << 1) + (s << 3) + (ch xor 48),ch = gc();return s * f;
	}
	template<typename type>inline void write(type x,char out)
	{
		if(!x) return putchar('0'),putchar(out),void(); if(x < 0) putchar('-'),x = -x;
		register int cnt = 0;while(x) output[++cnt] = x % 10,x /= 10; 
		throw(i,cnt,1) putchar(output[i] xor 48);return putchar(out),void();
	}
}
using namespace xin_io; static const int maxn = 1e6+10,inf = 1e9+7,mod = 998244353; static const ll llinf = 1e17+7;
namespace xin
{
	int n;
	int c[maxn],pos[maxn];
	int f[maxn],maxx;
	class xin_segment
	{
		private:
			#define ls(fa) (fa << 1)
			#define rs(fa) (fa << 1 | 1)
			int lim(int fa,int val)
			{
				if(t[fa].tag) return t[fa].s > val ? f[t[fa].s] : 0; 
				return t[rs(fa)].s < val ? lim(ls(fa),val) : (t[fa].lans + lim(rs(fa),val)) % mod;
			}
			inline void up(int fa)
			{
				t[fa].s = std::max(t[ls(fa)].s,t[rs(fa)].s);
				t[fa].lans = lim(ls(fa),t[rs(fa)].s);
			}
		public:
			class xin_tree{public:int s,lans,tag;}t[maxn];
			void build(int fa,int l,int r)
			{
				if(l == r) return t[fa].tag = 1,void(); //tag the leave point
				register int mid = l + r >> 1;
				build(ls(fa),l,mid); build(rs(fa),mid+1,r);
			}
			void modify(int fa,int l,int r,int pos,int val)
			{
				if(pos > r or pos < l) return;
				if(l == r) return t[fa].s = val,void();
				register int mid = l + r >> 1;
				modify(ls(fa),l,mid,pos,val); modify(rs(fa),mid+1,r,pos,val);
				up(fa);
			}
			int query(int fa,int l,int r,int ql,int qr)
			{
				if(ql > r or qr < l) return 0;
				if(ql <= l and qr >= r)
				{
					register int temp = maxx; maxx = std::max(maxx,t[fa].s);
					return lim(fa,temp);
				}
				register int mid = l + r >> 1,res = 0;
				res = (res + query(rs(fa),mid+1,r,ql,qr)) % mod; res = (res + query(ls(fa),l,mid,ql,qr)) % mod;
				return res;
			}
	}t;
	class xin_bit
	{
		private:
			#define lowbit(x) (x & -x)
		public:
			int s[maxn];
			inline void add(int x,int val)
			{for(register int i=x;i<=n;i+=lowbit(i)) s[i] += val;}
			inline int ask(int x)
			{int res = 0;for(register int i=x;i;i-=lowbit(i)) res += s[i];return res;}
	}bit;
	inline short main()
	{
	#ifndef ONLINE_JUDGE
		openfile();
	#endif
		n = get(); try(i,1,n) c[i] = get(),pos[c[i]] = i;
		t.build(1,1,n);
		try(i,1,n)
		{
			register int x = pos[i]; maxx = 0;
			f[i] = t.query(1,1,n,1,x);
			if(!f[i]) f[i] = 1;
			t.modify(1,1,n,x,i);
		}
		int ans = 0;
		throw(i,n,1)
		{
			if(bit.ask(n) == bit.ask(pos[i])) ans = (ans + f[i]) % mod;
			bit.add(pos[i],1);
		}
		cout<<ans<<endl;
		return 0;
	}
}
signed main(){return xin::main();}