水题，直接单调栈（谐音梗）。
考虑从 $[l,n]$ 转移到 $[l-1,n]$ ，注意到除了 $l$，只有在前一区间中出现在了栈顶，才有可能在新区间中出现在栈顶。维护在区间中所有出现在 $S$ 栈顶的元素，考虑 $l-1$ 对其影响：从前至后弹出不能导致 $l-1$ 弹出的元素，直到一个元素弹出了 $l-1$，此后 $l-1$ 对该区间无影响。
在计算到 $[l,n]$ 时，计算出所有 $[l,r]$，维护的是单调的位置序列，$r$ 对序列没有影响，二分 lowerbound 即可。
复杂度
$O(n\log n)$
Code
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
| #include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int mxn=500005;
int n,q;
int a[mxn],b[mxn],pos[mxn],ans[mxn];
pair<pii,int> qu[mxn];
int t[mxn],l;
int read()
{
int ret=0;char c=getchar();
while(c>'9'||c<'0')c=getchar();
while(c<='9'&&c>='0')ret=ret*10+c-'0',c=getchar();
return ret;
}
int find(int L,int R,int v)
{
int mid;
while(L<=R)
{
mid=L+R>>1;
if(t[mid]>v)R=mid-1;
else L=mid+1;
}
return R;
}
int main()
{
n=read(),q=read();
for(int i=1;i<=n;i++)a[i]=read();for(int i=1;i<=n;i++)b[i]=read();
for(int i=1;i<=q;i++)qu[i].first.first=-read(),qu[i].first.second=read(),qu[i].second=i;
sort(qu+1,qu+q+1);l=n+1;
for(int i=n,j=1,an;i&&(j<=q);i--)
{
while(l<=n&&b[i]>b[t[l]]&&a[t[l]]!=a[i])
++l;
t[--l]=i;an=l;
for(;j<=q&&qu[j].first.first==(-i);j++)
{
an=find(an,n,qu[j].first.second);
ans[qu[j].second]=an-l+1;
}
}
for(int i=1;i<=q;i++)printf("%d\n",ans[i]);
return 0;
}
|
假设我们有一个容器，向其中一个一个加入这些集合。
如果两个人会讨论，则一定是后加入那个集合所覆盖的范围一半在一个集合里，一半在集合外。而在出现这种情况之前，两个集合要么包含，要么交集为空。
那么如果我构造一种染色方案，使得每一道题，不同的覆盖方案染上不同的颜色，每一次看集合中颜色是否统一不就行了？
想得美
如果一个集合被该集合真包含，会被误判。
那我就避开这种情况的发生：我按集合大小从大到小排序，那后加入的集合就不可能真包含之前的集合。
那么如何染色呢？
每一次加入一个集合，如果没有被统计答案，则两个集合要么包含，要么交集为空，也就是说在这个集合加入的位置上覆盖情况相同。那么我给这个集合所包含的元素染上一个独一无二的颜色。
然后就愉快地结束了（越看越像暴力了）
复杂度
多一个集合多一种颜色。给这些点染色或判断是否新加入集合导致讨论是 $O(\sum k_i)$ 的，排序是 $O(n\log n)$ 的，整体复杂度 $O(n\log n+\sum k_i)$。
Code
经过调整仍丑陋的考场代码
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
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int read()
{
int ret=0;char c=getchar();
while(c>'9'||c<'0')c=getchar();
while(c<='9'&&c>='0')ret=ret*10+c-'0',c=getchar();
return ret;
}
struct node
{
int k,id;
vector <int> p;
friend bool operator < (node n1,node n2)
{
return n1.k>n2.k;
}
}a[1000001];
vector <int> mp[1000001];
int T,n;
int lst,col[1000001];
bool f1[1000001],f2[1000001];
int main()
{
T=read();
for(;T;T--)
{
memset(col,0,sizeof(col));
int ans1=0,ans2=0;
n=read();
for(int i=1;i<=n;i++)
{
a[i].k=read();a[i].p.clear();
for(int j=1,x;j<=a[i].k;j++)x=read(),a[i].p.push_back(x),a[i].id=i;
}
sort(a+1,a+1+n);for(int i=1;i<=n;i++)mp[i].clear();
for(int i=1;i<=n;i++)
{
lst=-1;
for(int j=0;j<a[i].k;j++)
{mp[a[i].p[j]].push_back(a[i].id);
if(lst>=0&&col[a[i].p[j]]!=lst)
{
ans1=a[i].id;
for(int x=0;x<mp[a[i].p[j]].size();x++)f1[mp[a[i].p[j]][x]]=1;
for(int x=0;x<mp[a[i].p[j-1]].size();x++)f2[mp[a[i].p[j-1]][x]]=1;
for(int x=1;x<=n;x++)if(f1[x]^f2[x])
{
ans2=x;
break;
}
memset(f1,0,sizeof(f1));
memset(f2,0,sizeof(f2));
break;
}
lst=col[a[i].p[j]];
col[a[i].p[j]]=i;
}
if(ans1)break;
}
if(ans1)printf("YES\n%d %d\n",ans1,ans2);
else puts("NO");
}
return 0;
}
|
彩蛋
网站最后几分钟崩了没交上，后来延时差点以为自己提交忘删调试信息。不过还好 AC 了。
都多久了才来写
T3 看了一眼，感觉不会，也没时间了，就没做。
最终分数：200。