丹钓战

倍增

给定一个很具体的操作，显然每次都是再重复计算，直接考虑倍增，从每个点出发第一个被成功的弹出，那个点所在的位置，倍增维护。

O(nlog⁡n)O(n\log n)

像这种重复操作的倍增，基本就是维护的是走多少合法得步数，可以走到得位置是什么。

又根据任意一个正整数都可以表示为二进制拆分，所以操作可行。

树状数组

O(nlog⁡n)O(n\log n)

zero

莫队

O(nn2)O(n \sqrt[2]{n})

zero

讨论

Alt text

直接考虑拥有同一元素的相邻两个集合快速判断包含性。

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
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
template<typename T>inline void read(T &x){
	x=0;T f=1;char ch=getchar();
	while(ch<48||ch>57){if(ch=='-'){f=-1;}ch=getchar();}
	while(ch>=48&&ch<=57){x=x*10+ch-48;ch=getchar();}
	x*=f;
}
template<typename T>inline void write(T x) {
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+48);
}
using namespace std;
const int N=1E6+8;
int T,n;
int k[N],a[N];
vector <int> p[N];
int cnt[N];
inline bool cmp(int x,int y) {
	return k[x]<k[y];
}
int vis[N];
int main(){
	//  freopen("discuss2.in","r",stdin);
//	freopen("discuss.out","w",stdout);
	cin>>T;
	while(T--){
		memset(vis,0,sizeof vis);
		memset(cnt,0,sizeof cnt);
		read(n);
		for_each(p,p+N,[](vector<int>& v){v.clear();});
		p->shrink_to_fit();
		for(int i=1;i<=n;i++){
			read(k[i]);
			for(int u=0;u<k[i];++u){
				int x;
				read(x);
				p[i].push_back(x);
			}  
			a[i]=i;
		}
		sort(a+1,a+n+1,cmp);
		bool flag=0;
		for(int t=1;t<=n&&!flag;t++){
			int i=a[t];
			if(k[i]==0) continue;
            if(t^1){
                for(int u=0;u<k[i];u++){
				    ++cnt[vis[p[i][u]]];
			    }
                for(int u=0;u<k[i];u++){
			        int g=vis[p[i][u]];
			        if(cnt[g]<k[g]&&cnt[g]<k[i]){
			        	puts("YES");
			        	write(i); putchar(' '); write(g); puts("");
			        	flag=1;
			        	break;
			        }
			    }
                for(int u=0;u<k[i];u++){
		        	--cnt[vis[p[i][u]]];
		        	vis[p[i][u]]=i;
		        }
            }
            else{
               for(int u=0;u<k[i];u++){
		        	vis[p[i][u]]=i;
		        } 
            }
		}
		if(!flag)puts("NO");
	}
	return 0;
}

__END__