k个代表

k个代表是一个我原创的黑科技(其实说不定其他人也有类似做法) 取这个名字是为了【政治敏感】

我感觉k个代表的含义更贴近于“面向数据动态分类，答案一定在某类中”

1 入门

我们来看一个最简单的例子

（强行被称为k个代表）

有n个正整数 a₁-a_n 你要求出对a_i (1<=i<=n)最大的 a_k 使得 a_k!=a_i 没有输出-1 n=1e6

我们可以顺着扫一遍 维护2个数 分别是x,y x表示当前最大的数 y表示当前不同于x的最大的数 初始x=y=-1

若a_i==x 输出y 否则输出x

 1 using namespace std;
 2 int n,a[1000005],x=-1,y=-1;
 3 int main(){
 4     scanf("%d",&n);
 5     for(int i=1;i<=n;++i){
 6         scanf("%d",a+i); 
 7         if(a[i]>x)y=x,x=a[i];
 8         else if(a[i]>y)y=a[i];
 9         if(a[i]==x)printf("%d\n",y);
10         else printf("%d\n",x);
11     }
12     return 0;
13 }

 下面我们看一些正常一点的例子

2 静态k个代表

我称对每种代表只有一次写入 没有修改的k个代表为 静态k个代表

我们来看一个优秀的静态k个代表的例子

题目：http://acm.nflsoj.com/problem/72

给出一个只包含大写字母B，C，S的字符串，请找到最长的子串，要求这个子串满足以下两个条件中的一个：

• 该子串中B的出现次数不等于C的出现次数，C的出现次数不等于S的出现次数，S的出现次数不等于B的出现次数。
• 该子串只包含一种字符。

数据范围 1<=n<=1e6

std写的是树状数组 O(nlogn) 这种做法的题解：http://acm.nflsoj.com/blog/youyl/blog/100

我用了一种O(n)的做法 ：10个代表

全相等那种情况略

对于S(i,0)-S(i,1)=x_i,S(i,1)-S(i,2)=y_i,S(i,2)-S(i,0)=z_i

我们有：(j,i]可行<==>x_i!=x_j,y_i!=y_j,z_i!=z_j

所以我们对每个i,找到最小的j，0<=j< i, x_i!=x_j, y_i!=y_j, z_i!=z_j, 然后用i-j更新答案即可

对于x_i!=0,y_i!=0,z_i!=0,j=0

对于x_iy_iz_i恰好2个等于0，不可能，因为x+y+z=0

对于x_iy_iz_i恰好1个等于0

考虑x=0的情况

我们需要维护3个代表即可：

第一个:最小的p使x_p!=0

对于y_p=y的情况，我们知道了这组为(0,y_p,-y_p),对这一组找一个最小代表即可

对于z_p=z的情况，我们知道了这组为(0,-z_p,z_p),对这一组找一个最小代表即可

y=0,z=0情况同x=0

对x=0,y=0,z=0 找一个代表即可

一共是10个代表

 1 #define X  first
 2 #define Y  second
 3 using namespace std;
 4 int s[1000005][3],n,ans=1,l[3];
 5 int f[10],X[10],Y[10],Z[10];
 6 void upd(int k){if(k>ans)ans=k;}
 7 int main(){
 8     scanf("%d",&n),getchar();
 9     for(int i=1;i<=n;++i){
10         char c=getchar();
11         s[i][0]=s[i-1][0],s[i][1]=s[i-1][1],s[i][2]=s[i-1][2];
12         int k=(c>'C')+(c>'B');
13         ++s[i][k];
14         if(l[k])upd(i-l[k]+1);
15         else l[0]=l[1]=l[2]=0,l[k]=i;
16     }
17     for(int i=1;i<=n;++i){
18         int x=s[i][0]-s[i][1],y=s[i][1]-s[i][2],z=s[i][2]-s[i][0];
19         int k=0;
20         if(x){
21             k^=1;
22             if(!f[1])f[1]=i,X[1]=x,Y[1]=y,Z[1]=z;
23             else{
24                 if(!f[2]&&Y[1]!=y&&-Y[1]!=z)f[2]=i,X[2]=x,Y[2]=y,Z[2]=z;
25                 if(!f[3]&&-Z[1]!=y&&Z[1]!=z)f[3]=i,X[3]=x,Y[3]=y,Z[3]=z;
26             }
27         }
28         if(y){
29             k^=2;
30             if(!f[4])f[4]=i,X[4]=x,Y[4]=y,Z[4]=z;
31             else{
32                 if(!f[5]&&X[4]!=x&&-X[4]!=z)f[5]=i,X[5]=x,Y[5]=y,Z[5]=z;
33                 if(!f[6]&&-Z[4]!=x&&Z[4]!=z)f[6]=i,X[6]=x,Y[6]=y,Z[6]=z;
34             }
35         }
36         if(z){
37             k^=4;
38             if(!f[7])f[7]=i,X[7]=x,Y[7]=y,Z[7]=z;
39             else{
40                 if(!f[8]&&X[7]!=x&&-X[7]!=y)f[8]=i,X[8]=x,Y[8]=y,Z[8]=z;
41                 if(!f[9]&&-Y[7]!=x&&Y[7]!=y)f[9]=i,X[9]=x,Y[9]=y,Z[9]=z;
42             }
43         }
44         if(!k){
45             if(f[0])upd(i-f[0]);
46             continue;
47         }
48         if(k==7){
49             if(!f[0])f[0]=i;
50             upd(i);
51             continue;
52         }
53         if(!x){
54             if(!f[1]) continue;
55             if(Y[1]==y){if(f[2])upd(i-f[2]);}
56             else if(Z[1]==z){if(f[3])upd(i-f[3]);}
57             else upd(i-f[1]);
58             continue;
59         } 
60         if(!y){
61             if(!f[4]) continue;
62             if(X[4]==x){if(f[5])upd(i-f[5]);}
63             else if(Z[4]==z){if(f[6])upd(i-f[6]);}
64             else upd(i-f[4]);
65             continue;
66         } 
67         if(!z){
68             if(!f[7]) continue;
69             if(X[7]==x){if(f[8])upd(i-f[8]);}
70             else if(Y[7]==y){if(f[9])upd(i-f[9]);}
71             else upd(i-f[7]);
72         }    
73     }
74     printf("%d\n",ans);
75     return 0;
76 }

用时是std的10分之一 而且非常好写（你要学会复制粘贴）

再看一个例子

线性基其实也是一种静态k个代表（真不要脸）

这里不介绍 自行搜索

当然下文会给出功能更加强大的线性基

3 动态k个代表

我们来看一个例子

(这里假设你已经会了线性基)

题目来源whzzt模拟赛

蒜头是一位优秀的 OI 选手。
自古以来，迷人的星空总是吸引着许多天文学的爱好者。顺着星星的指引，明天的蒜头将会遇到一道
有趣的题，和蒜头曾经出过的一道题一样有趣。
给一个长度为 n 的序列 a，q 次询问在 a[l...r] 中选择若干个数 (可以不选) 和 d 异或所能得到的最
大值。

数据范围1<=n,q<=1e6,1<=a_i<2^30

我们发现线性基是静态的 太浪费了

于是想到可以动态改变那30个代表 我们尽量找比较新的

我们插入数的时候 到某一位时 若比原代表更新 就把它替换掉 拿原代表向下插

类似冒泡排序

因为只有老数被新数异或 所以正确性显然

这题std和我做法一样 所以再贴一下whzzt的题解

“时间复杂度瓶颈在于我们要表示出 O(loga) 个线性基。

考虑我们之前维护端点的过程，那么后 i 个端点实际上就是一个

大小为 i 的线性无关组。

容易发现，我们将位置在前面的数异或位置在后面的数，并不会

对我们的答案产生影响。所以实际上我们仍然可以维护线性基，

并且只需维护 1 个。

实现上来说，只要同时存在两个最高位相同的数时，用前面的异

或后面的即可。

时间复杂度 O((n + q)loga) 。”

 1 #define pb   push_back
 2 using namespace std;
 3 int n,q,a[1000005],f[31],l[1000005],r[1000005],d[1000005];
 4 vector<int> v[1000005];
 5 int main(){
 6     scanf("%d",&n);
 7     for(int i=1;i<=n;++i)scanf("%d",a+i);
 8     scanf("%d",&q);
 9     for(int i=1;i<=q;++i)scanf("%d%d%d",l+i,r+i,d+i),v[r[i]].pb(i);
10     for(int i=1;i<=n;++i){
11         int k=i;
12         for(int j=29;j>=0;--j){
13             if((a[k]&(1<<j))){
14                 if(k>f[j])a[f[j]]^=a[k],swap(f[j],k);
15                 else a[k]^=a[f[j]];
16             }
17         }
18         for(int j=0;jj){
19             int o=v[i][j];
20             for(int k=29;k>=0;--k)if(l[o]<=f[k]&&!(d[o]&(1<a[f[k]];
21         }
22     }
23     for(int i=1;i<=q;++i)printf("%d\n",d[i]);  
24     return 0;
25 }

4 一种代替做法

有的时候我们实在想不出怎么划分k个代表 这时有一个多一个log但是好想好实现的划分方法 可以解决部分问题

（通常来说 这类问题其实都有O(1)划分方法）

我们发现x!=y <==>存在k使得(x&(1<

于是划分方法为：第2k+1个代表是(x&(1<

5 拓展

其实某个代表不一定是一个数 可能是一个集合或者别的什么东西

暂时没有好的例子所以没有写在这里

===upd

加了一道我出的非常难的k个代表题目

https://acm.nflsoj.com/problem/379

（idea和solution来自我，题面及时空范围来自lqs2015）

如果因为权限看不到题面可以看这个：

（markdown格式，懒得改了）

2000ms 256MiB

###题目描述

众所周知，蒟蒻总是崇拜神犇。在 NFLS 里，有 $n$ 个蒟蒻，编号为 $1,2,\cdots,n$。lqs 是其中的一员。他们每个人都有**一个**崇拜的神犇，每个人崇拜的神犇都是**FizzyDavid, Ohweonfire, diamond_duke**中的一个。编号为 $i$ 个蒟蒻对他崇拜的神犇的崇拜度为 $A_i$。

wzy 是 NFLS 的另外一位神犇，他也希望有蒟蒻来崇拜他。现在 wzy 想要选择编号为一个区间的蒟蒻，使得他们崇拜他。对于编号为 $[l,r]$ 的蒟蒻来说，如果存在两个神犇，崇拜他们的蒟蒻个数相同（可能为 $0$），那么这个区间的不平衡度为 $0$。否则这个区间的不平衡度为这个区间中所有蒟蒻对他们崇拜的神犇的崇拜度的异或和，即 $A_l \oplus A_{l+1} \oplus \cdots \oplus A_r$，其中 $\oplus$ 是异或操作。

现在 wzy 想知道对于所有的 $x(1 \le x \le n)$，以 $x$ 为右端点的区间的不平衡度的最大值，因为不平衡度越大，wzy 越好下手。神犇总是日理万机，所以他没时间做这个。因为你是 wzy 的粉丝，所以他把这个任务交给了你。

由于一些原因，你可能需要顺序回答问题，具体请见输入格式。

###输入格式

第一行两个整数 $n,opt$，表示蒟蒻的个数，若 $opt=0$，则不强制在线，否则表示强制在线。如果 $opt=2$ 则表示一种特殊的部分分，请见“约束”。

第二行有 $n$ 个数字，第 $i$ 个数字是 $0,1,2$。表示第 $i$ 个蒟蒻崇拜的神犇，$0$ 表示 **FizzyDavid**，$1$ 表示**Ohweonfire**，$2$ 表示**diamond_duke**.

如果 $opt \neq 0$，记上面这 $n$ 个数的序列为 $p_1,p_2,\cdots,p_n$，那么真实的数字 $=(lastans \oplus p_i) \mod 3$，否则输入的 $p_i$ 就是真实的数字。

第三行为 $n$ 个数 $A_1,A_2,\cdots,A_n$。其意义如题。

如果 $opt \neq 0$，那么真实的数字 $=lastans \oplus A_i$，否则输入的 $A_i$ 就是真实的数字，其中，$lastans$ 是上一次计算的结果，初始时为 $0$。

###输出格式

输出共一行，有 $n$ 个数，第 $i$ 个数表示以 $i$ 为右端点的区间的不平衡度的最大值。

###样例输入 1

```

8 0

0 1 2 2 1 1 0 0

2 3 7 1 4 5 3 2

```

###样例输出 1

```

0 0 0 5 2 6 7 4

```

###样例解释 1

下面是每个位置为右端点取到的最大值区间：

$[1,1]$（此时由于膜另外两位神犇的都是0人，因此答案为0）,

$[2,2]$（原因同上）,

$[3,3]$（原因同上）,

$[2,4]$,

$[3,5]$,

$[1,6]$,

$[2,7]$,

$[6,8]$.

###样例输入 2

```

10 0

0 0 0 0 0 0 0 0 0 0

1 2 4 8 16 32 64 128 256 512

```

###样例输出 2

```

0 0 0 0 0 0 0 0 0 0

```

###样例解释 2

**FizzyDavid**粉丝群，由于一直没人膜另外两个神犇，因此答案都为 $0$。

###数据范围与约定

对于 $100\%$ 的数据 $n \le 300000,A_i \le 10^9$。

* $subtask1(20pts)：n \le 2000$

* $subtask2(20pts)：$保证解密之后，所有人只膜 **FizzyDavid** 和 **Ohweonfire**，为了方便选手判断这一档部分分，$subtask2$ 的所有数据中 $opt=2$。

* $subtask3(20pts)：opt=0$

* $subtask4(20pts)：n \le 10 ^ 5$

* $subtask5(20pts)：$无特殊限制

我有时间了放上解答 但是先提供std

  1 //Relive your past life.
  2 //Face your demons.
  3 //The past is never dead,it is not even past.
  4 //The memories are not only the key to the past but...also to the future.
  5 //coded in Rusty Lake
  6 #include
  7 #include
  8 #include
  9 #include
 10 #include
 11 #include
 12 #include
 13 #include
 14 #include
 15 #include
 16 #include
 17 #include
 18 #include
 19 #include
 20 #include
 21 #include
 22 #include
 23 #include
 24 #include
 25 #include
 26 #include
 27 #include
 28 #include
 29 #include
 30 #include
 31 #include
 32 #include
 33 #include
 34 #include
 35 #include
 36 #include
 37 #include
 38 #include
 39 #include
 40 #include
 41 #include
 42 #include

转载于:https://www.cnblogs.com/skylineidolon/p/8697351.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！