test20190504

Posted on | Edited on | Views:

据说 是 $noip$ 难度.

题面

$find$

  • 比较简单.按照 $x$ 坐标排序后,就是以 $y$ 坐标为关键字做一个 $LIS​$ .
  • $O(nlogn)​$.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
inline int read()
{
	int x=0,k=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') k=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	return k*x;
}
const int MAXN=1e6+10;
int n=0,my,y[MAXN],Y[MAXN];
pair<int,int> p[MAXN];
int bit[MAXN];
#define lowbit(x) x&(-x)
inline void add(int x,int c)
{
	for(; x<=my; x+=lowbit(x))
		bit[x]=max(bit[x],c);
}
inline int sum(int x)
{
	int s=0;
	for(; x; x-=lowbit(x))
		s=max(s,bit[x]);
	return s;
}
int main()
{
	freopen("find.in","r",stdin);
	freopen("find.out","w",stdout);
	int N=read();
	for(int i=1; i<=N; ++i)
	{
		int a=read(),b=read();
		if(a<0 || b<0)
			continue;
		++n;
		p[n].first=a;
		Y[n]=y[n]=b;
	}
	sort(Y+1,Y+1+n);
	my=unique(Y+1,Y+1+n)-Y-1;
	for(int i=1; i<=n; ++i)
		p[i].second=lower_bound(Y+1,Y+1+my,y[i])-Y;
	sort(p+1,p+1+n);
	int ans=0;
	for(int i=1; i<=n; ++i)
	{
		int ky=p[i].second;
		int mx=sum(ky);
		ans=max(ans,mx+1);
		add(ky,mx+1);
	}
	cout<<ans<<endl;
	return 0;
}

$walk$

  • 是个套路题.
  • 标算套路:因为询问给出的 $v$ 最大是 $10^{18}$ ,所以走不为 $1$ 的边,最多走 $60$ 次就会变成 $0$ .
  • 于是只需要用并查集把边权为 $1$ 连接的两个点并在一起,然后跳的时候暴力跳,跳成 $0$ 或者到终点就退出.
  • 这样最多跳 $60$ 次,而且大多数时候跳不满,所以可以过.
  • 我的做法相当假.注意到这个操作是可合并的,直接树剖 + 线段树维护区间边权乘积.
  • 但是区间乘积可能会爆掉 $long\ long$ .
  • 于是每次 $pushup$ 的时候都让乘积与 $0$ 取 $max$ .这样一段爆掉的区间乘积(大概率)是 $0$ .跳的时候遇到了就直接输出 $0$ .
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
inline ll read()
{
	ll x=0,k=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') k=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	return k*x;
}
const int MAXN=2e5+10;
int n,Q;
int ecnt=0,head[MAXN],to[MAXN<<1],nx[MAXN<<1],fa[MAXN];
int dep[MAXN];
inline void addedge(int u,int v,ll w)
{
	++ecnt;
	to[ecnt]=v;
	nx[ecnt]=head[u];
	val[ecnt]=w;
	head[u]=ecnt;
}
ll wp[MAXN];
int dfn[MAXN],dfnidx=0,rnk[MAXN],siz[MAXN],mxson[MAXN],top[MAXN];
void dfs1(int u,int f)
{
	fa[u]=f;
	siz[u]=1;
	dep[u]=dep[f]+1;
	for(int i=head[u]; i; i=nx[i])
	{
		int v=to[i];
		if(v==f)
			continue;
		dfs1(v,u);
		siz[u]+=siz[v];
		if(siz[v]>siz[mxson[u]])
			mxson[u]=v;
	}
}
void dfs2(int u,int tp)
{
	dfn[u]=++dfnidx;
	rnk[dfnidx]=u;
	top[u]=tp;
	if(mxson[u])
		dfs2(mxson[u],tp);
	for(int i=head[u]; i; i=nx[i])
	{
		int v=to[i];
		if(v!=mxson[u] && v!=fa[u])
			dfs2(v,v);
	}
}
ll prod[MAXN<<2];
#define root prod[o]
#define lson prod[o<<1]
#define rson prod[o<<1|1]
void pushup(int o)
{
	root=lson*rson;
	root=max(root,0LL);
}
void bd(int o,int l,int r)
{
	if(l==r)
	{
		root=wp[rnk[l]];
		return;
	}
	int mid=(l+r)>>1;
	bd(o<<1,l,mid);
	bd(o<<1|1,mid+1,r);
	pushup(o);
}
void update(int o,int l,int r,int pos,ll c)
{
	if(l==r)
	{
		root=c;
		return;
	}
	int mid=(l+r)>>1;
	if(pos<=mid)
		update(o<<1,l,mid,pos,c);
	else
		update(o<<1|1,mid+1,r,pos,c);
	pushup(o);
}
ll query(int o,int l,int r,int L,int R)
{
	ll res=1;
	if(l>R || L>r)
		return 1;
	if(L<=l && r<=R)
		return max(0LL,root);
	int mid=(l+r)>>1;
	if(L<=mid)
	{
		res*=query(o<<1,l,mid,L,R);
		res=max(res,0LL);
	}
	if(R>mid)
	{
		res*=query(o<<1|1,mid+1,r,L,R);
		res=max(res,0LL);
	}
	return res;
}
void solve()
{
	int idx=n;
	for(int i=1; i<n; ++i)
	{
		int u=read(),v=read();
		ll w=read();
		++idx;
		addedge(u,idx,0);
		addedge(idx,u,0);
		addedge(idx,v,0);
		addedge(v,idx,0);
		wp[idx]=w;
	}
	for(int i=1; i<=n; ++i)
		wp[i]=1;
	dfs1(1,0);
	dfs2(1,1);
	bd(1,1,idx);
	while(Q--)
	{
		int tp=read();
		if(tp==1)
		{
			int x=read(),y=read();
			ll v=read();
			while(top[x]!=top[y])
			{
				if(dep[top[x]]<dep[top[y]])
					swap(x,y);
				ll p=query(1,1,idx,dfn[top[x]],dfn[x]);
				if(p<=0)
				{
					puts("0");
					continue;
				}
				v/=p;
				x=fa[top[x]];
			}
			if(dep[x]<dep[y])
				swap(x,y);
			ll p=query(1,1,idx,dfn[y],dfn[x]);
			if(p<=0)
			{
				puts("0");
				continue;
			}
			v/=p;
			printf("%lld\n",v);
		}
		else
		{
			int p=read();
			ll c=read();
			update(1,1,idx,dfn[p+n],c);
		}
	}
}
int main()
{
	freopen("walk.in","r",stdin);
	freopen("walk.out","w",stdout);
	n=read();
	Q=read();
	solve();
	return 0;
}

$sunset$

  • 想出了正确做法,但今天是按照 $5$ 个小时的节奏在打的,实际是 $3.5h$ ,只剩了 $20min$ ,就没写了.
  • 显然每个联通块可以分开做.对于一个联通块,做一颗 $dfs​$ 树,因为是无向图,所以除了树边之外就只有返祖边.
  • 返祖边会形成一个环,如果这个环的大小为偶(通过 $dep​$ 之差判断),显然没有作用.若为奇,就把环上的边都打上标记.
  • 询问时,若 $dep_x,dep_y$ 奇偶性不同,直接走树边长度就是奇数.否则如果两者路径上有被标记的边,走一个奇环再出来,长度也是奇数.
  • 如果两种情况都不满足,就无法找到长度为奇数的路径.