题解 U534155 【打磨珍珠】

发表于 更新于 分类于 ， 阅读次数： 本文字数： 2.6k 阅读时长 ≈ 9 分钟

题目链接：打磨珍珠。

关于题目：作为 T2，很简单的算法题。

应用算法：离散化，差分，离线。

\(\ \ \ \ \ \ \)这道题虽然思维难度和算法难度都不大，但是细节却比较多，我们就从分析题面入手，循序渐进地来说。

  • 一、分析题面：

    • 1、命令：就相当于对于一段区间的区间加 \(1\)

    • 2、条件：对于连续的 \(k\) 个点，每个点的值相同且区间和 \(\in(l,r)\)。

    • 3、输出：这样连续的 \(k\) 个点的个数。

    • 4、数据范围（这里就仅讲解 \(AC\) 的做法，敬请谅解）：对于 \(100\%\) 的数据，\(1\leqslant n \leqslant 10^6\)，\(1\leqslant k \leqslant 1000\)，\(0\leqslant l < r \leqslant 10^6\)，最远能移动到离原点 \(1000000000\) 的珍珠面前。

\(\ \ \ \ \ \ \)由数据范围和空间限制可知，我们开不下 \(1000000000\) 的数组，对于这类空间上的“超限”，我们可以很自然地想到离散化这种非常常用的算法，相信大佬们都会，具体思想就不在这里赘述了，不会的同学可以自行查找资料学习。

\(\ \ \ \ \ \ \)由数据范围和时间限制可知，我们不可能运用 \(O(n\times l)\) 的算法，那么既然是区间加，且全部加完再进行统计，很自然地就能想到运用差分维护 \(+\) 离线统计的做法，相信大佬们都会，具体思想也不在这里赘述了，不会的同学可以自行查找资料学习。

\(\ \ \ \ \ \ \)然后就没了，剩下的就是应用算法模拟题意。

  • 二、处理过程：既然已经很清晰地知道了需要用的算法和进行的操作，接下来就可以开始具体的处理了。

    • 1、读入……这个就不用我来说了吧。

    • 2、一个小小的预处理：既然运用了差分，求区间和过于麻烦，根据 \(k\) 个点的值相同，我们直接判断每个点的值不就得了。\(\\ \ \ \ \ \ \ \because sum \in(l,r)\\ \ \ \ \ \ \ \therefore a_i \in\left[ \left\lfloor\dfrac{l}{k}\right\rfloor+1,\left\lceil\dfrac{r}{k}\right\rceil-1 \right]\\\) 

      1
      2
      3
      4
      5
      6
      7
      8
      9
        l=l/k+1;
      if(r%k)
      {
      		r=r/k;
      }
      else
      {
      		r=r/k-1;
      }

    • 3、处理命令：

      • （1）、我们设 \(o\) 代表现在的坐标，\(v\) 表示命令中的移动次数。\(a_{i,1}\) 表示第 \(i\) 次命令的差分数组需要减 \(1\) 的坐标，\(a_{i,2}\) 表示第 \(i\) 次命令的差分数组需要加 \(1\) 的坐标。\(\\ \ \ \ \ \ \ \)对于向右侧移动的命令： 
        1
        2
           a[i][1]=o+1;
        a[i][2]=o+v;
        \(\ \ \ \ \ \ \)同理，对于向左侧移动的命令： 
        1
        2
           a[i][2]=o-1;
        a[i][1]=o-v;
      • （2）、我们设 \(b\) 数组为离散化所排序去重统计的数组，所以需要把每个 \(a_{i,1}\) 和 \(a_{i,2}\) 放入 \(b\) 数组。 
        1
        2
           b[(i<<1)-1]=a[i][1];
        b[(i<<1)]=a[i][2];

    • 4、离散化：先排序，再去重，设 \(p1\) 表示 \(a_{i,1}\) 离散化后的编号，\(p2\) 表示 \(a_{i,2}\) 离散化后的编号，设 \(c\) 数组表示 \(p1->a_{i,1}\) 或 \(p2->a_{i,2}\)的反向映射，并把 \(a_{i,1}\) 用 \(p1\) 赋值，\(a_{i,2}\) 用 \(p2\) 赋值。 

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
        sort(b+1,b+((n<<1)|1));
      cnt=unique(b+1,b+((n<<1)|1))-b-1;
      for(int i=1;i<=n;i++)
      {
      		int p1=lower_bound(b+1,b+cnt+1,a[i][1])-b;
      		int p2=lower_bound(b+1,b+cnt+1,a[i][2])-b;
      		c[p1]=a[i][1];
      		c[p2]=a[i][2];
      		a[i][1]=p1;
      		a[i][2]=p2;
      }

    • 5、差分：设 \(d\) 数组为差分数组，利用一下Manacher算法在每两个字符中间插入一个 # 的思想，我们也把任意两个差分的点之间的区间留出来，这样，把差分的编号扩大二倍就好了。 

      1
      2
      3
      4
      5
        for(int i=1;i<=n;i++)
      {
      		d[(a[i][1]<<1)]+=1;
      		d[(a[i][2]<<1)+1]-=1;
      }

    • 6、还原：设 \(e\) 数组为差分还原后的数组，直接加回来就好。 

      1
      2
      3
      4
        for(int i=1;i<=(cnt<<1);i++)
      {
      		e[i]=e[i-1]+d[i];
      }

    • 7、现在，\(e\) 数组里有 \(2n-1\) 个数，分别表示 \(n\) 个点的打磨次数和 \(n-1\) 个点之间的区间的打磨次数，但是由于开始或结束打磨的点可能相邻，就导致了 \(e\) 数组里存在某些区间的实际长度为 \(0\) 的区间，这些区间没有意义，不能参与统计答案。所以，我们就需要去除这些区间并将点和区间分别统计，用以统计答案。

      \(\ \ \ \ \ \ \)我们设 \(f_{0,i}\) 表示第 \(i\) 个能参与统计答案的元素为点，这个点的打磨次数，\(f_{1,i}\) 表示第 \(i\) 个能参与统计答案的元素为区间，这个点的打磨次数。设 \(g_i\)表示第 \(i\) 个能参与统计答案的元素为点，这个点对于原始的的坐标的映射。设 \(o\) 表示现在加入的是第几个能参与统计答案的元素。设 \(i\) 是对 \(e\) 数组偶数项的遍历。

      • 如果相邻，去掉中间区间： 
        1
        2
             f[0][++o]=e[i+2];
        g[o]=c[((i+1)>>1)+1];
      • 如果不相邻，保留中间区间： 
        1
        2
        3
             f[1][++o]=e[i+1];
        f[0][++o]=e[i+2];
        g[o]=c[((i+1)>>1)+1];

    • 8、统计答案：设 \(s\) 为当前符合条件的珍珠串的长度。先判断第 \(i\) 个参与统计答案的元素的打磨次数符合条件,由于 \(f_{0,i}\) 和 \(f_{1,i}\) 中有一个为零，把二者加到一起判断就好：

      • 如果为点：
        • （1）和前一个元素不同且和后一个元素相同：重新开启一个新的序列，存在 \(1\) 个符合标准的珍珠。 
          1
          s=1;
        • （2）和前一个元素相同且和后一个元素相同：继续当前的序列，加入 \(1\) 个符合标准的珍珠。 
          1
          s+=1;
        • （3）和前一个元素相同且和后一个元素不同：继续当前的序列，加入 \(1\) 个符合标准的珍珠并统计答案。 
          1
          2
          3
          4
          5
          s+=1;
          if(s>=k)
          {
          	ans+=s-k+1;
          }
        • （4）和前一个元素不同且和后一个元素不同：重新开启一个新的序列，存在 \(1\) 个符合标准的珍珠并统计答案。 
          1
          2
          3
          4
          5
               s=1;
          if(s>=k)
          {
          		ans+=s-k+1;
          }
      • 如果为区间：
        • （1）和前一个点不同且和后一个点相同：重新开启一个新的序列，存在区间长度个符合标准的珍珠。 
          1
          s=g[i+1]-g[i-1]-1;
        • （2）和前一个点相同且和后一个点相同：继续当前的序列，加入区间长度个符合标准的珍珠。 
          1
          s+=g[i+1]-g[i-1]-1;
        • （3）和前一个点相同且和后一个点不同：继续当前的序列，加入区间长度个符合标准的珍珠并统计答案。 
          1
          2
          3
          4
          5
          s+=g[i+1]-g[i-1]-1;
          if(s>=k)
          {
          	ans+=s-k+1;
          }
        • （4）和前一个点不同且和后一个点不同：重新开启一个新的序列，存在区间长度个符合标准的珍珠并统计答案。 
          1
          2
          3
          4
          5
               s=g[i+1]-g[i-1]-1;
          if(s>=k)
          {
          ans+=s-k+1;
          }

    • 9、输出……这个也就不用我来说了吧。

  • 三、代码：在处理过程中已经给出了最核心的部分代码，但是还是有一些小的细节没有给出，详见注释吧（码风不喜勿喷）： 

    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
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    #include<bits/stdc++.h>
    #define in inline
    #define re register
    #define N 1000010
    #define M 2000010
    using namespace std;
    int n,k,l,r,o,a[N][3],b[M],cnt,c[M],d[(M<<1)],e[(M<<1)],ans,f[2][(M<<1)],g[(M<<1)],s;
    //每个数组或变量的含义详见处理过程。
    in int qread()
    //快读
    {
        	int x=0,f=1;
        	int c=getchar();
        	while(c<'0'||c>'9')
        	{
        	    if(c=='-')f=-1;
        	    c=getchar();
        	}
        	while(c>='0'&&c<='9')
        	{
        	    x=(x<<1)+(x<<3)+(c^48);
        	    c=getchar();
        	}
        	return x*f;
    }
    in void qwrite(int x)
    //快写
    {
    		if(x<0)
    		{
    			putchar('-');
    			x=-x;
    			qwrite(x);
    		}
    		else
    		{
    			if(x>9)
    			{
    				qwrite(x/10);
    			}
    			putchar(x%10+'0');
    		}
    }
    signed main()
    {
    		n=qread();
    		k=qread();
    		l=qread();
    		r=qread();
    		//读入
    		l=l/k+1;
    		if(r%k)
    		{
    			r=r/k;
    		}
    		else
    		{
    			r=r/k-1;
    		}
    		//一个小小的预处理
    		for(re int i=1;i<=n;i++)
    		{
    			char c;
    			cin>>c; 
    			int v=qread();
    			if(c=='R')
    			{
    				a[i][1]=o+1;
    				a[i][2]=o+v;
    				b[(i<<1)-1]=a[i][1];
    				b[(i<<1)]=a[i][2];
    				o=o+v;
    			}
    			if(c=='L')
    			{
    				a[i][2]=o-1;
    				a[i][1]=o-v;
    				b[(i<<1)-1]=a[i][1];
    				b[(i<<1)]=a[i][2];
    				o=o-v;
    			}
    		}
    		//处理命令
    		o=1;
    		//一个小细节，由于后面还要用到o，所以在这里需要先赋一个值以确保后续使用的正确性
    		sort(b+1,b+((n<<1)|1));
    		cnt=unique(b+1,b+((n<<1)|1))-b-1;
    		for(re int i=1;i<=n;i++)
    		{
    			int p1=lower_bound(b+1,b+cnt+1,a[i][1])-b;
    			int p2=lower_bound(b+1,b+cnt+1,a[i][2])-b;
    			c[p1]=a[i][1];
    			c[p2]=a[i][2];
    			a[i][1]=p1;
    			a[i][2]=p2;
    		}
    		//离散化
    		for(re int i=1;i<=n;i++)
    		{
    			d[(a[i][1]<<1)]+=1;
    			d[(a[i][2]<<1)+1]-=1;
    		}
    		//差分
    		for(re int i=1;i<=(cnt<<1);i++)
    		{
    			e[i]=e[i-1]+d[i];
    		}
    		//还原
    		f[0][1]=e[2];
    		g[1]=c[1];
    		//一个小细节，对于f[0][1]和g[1]的初始化。e[2]肯定是第一个点，所以e[2]赋给f[0][1]，c[1]赋给g[1]
    		for(re int i=2;i<(cnt<<1);i+=2)
    		{
    			if(c[(i>>1)+1]-c[i>>1]==1)
    			{
    				f[0][++o]=e[i+2];
    				g[o]=c[((i+1)>>1)+1];
    			}
    			else
    			{
    				f[1][++o]=e[i+1];
    				f[0][++o]=e[i+2];
    				g[o]=c[((i+1)>>1)+1];
    			}
    		}
    		//处理一下区间
    		for(re int i=1;i<=o;i++)
    		{
    			if(l<=(f[0][i]|f[1][i])&&(f[0][i]|f[1][i])<=r)
    			{
    				if(f[0][i])
    				{
    					if(f[0][i]^(f[0][i-1]|f[1][i-1])&&f[0][i]==(f[0][i+1]|f[1][i+1]))
    					{
    						s=1;
    						continue;
    					}
    					if(f[0][i]==(f[0][i-1]|f[1][i-1])&&f[0][i]==(f[0][i+1]|f[1][i+1]))
    					{
    						s+=1;
    						continue;
    					}
    					if(f[0][i]==(f[0][i-1]|f[1][i-1])&&f[0][i]^(f[0][i+1]|f[1][i+1]))
    					{
    						s+=1;
    						if(s>=k)
    						{
    							ans+=s-k+1;
    						}
    						continue;
    					}
    					if(f[0][i]^(f[0][i-1]|f[1][i-1])&&f[0][i]^(f[0][i+1]|f[1][i+1]))
    					{
    						s=1;
    						if(s>=k)
    						{
    							ans+=s-k+1;
    						}
    						continue;
    					}
    				}
    				else
    				{
    					if(f[1][i]^f[0][i-1]&&f[1][i]==f[0][i+1])
    					{
    						s=g[i+1]-g[i-1]-1;
    						continue;
    					}
    					if(f[1][i]==f[0][i-1]&&f[1][i]==f[0][i+1])
    					{
    						s+=g[i+1]-g[i-1]-1;
    						continue;
    					}
    					if(f[1][i]==f[0][i-1]&&f[1][i]^f[0][i+1])
    					{
    						s+=g[i+1]-g[i-1]-1;
    						if(s>=k)
    						{
    							ans+=s-k+1;
    						}
    						continue;
    					}
    					if(f[1][i]^f[0][i-1]&&f[1][i]^f[0][i+1])
    					{
    						s=g[i+1]-g[i-1]-1;
    						if(s>=k)
    						{
    							ans+=s-k+1;
    						}
    						continue;
    					}
    				}
    			}
    		}
    		//统计答案
    		qwrite(ans);
    		putchar('\n');
    		//输出答案
    		return 0;
    }
    U4j2jJ.png

U4j79O.png
U4jXDA.png