今天做了P17828，学习了段级双指针。

看到本题，我的第一想法是展开字符串，并用双指针统计修改个数

代码如下

点击查看代码
#include
using namespace std;
int n;
const int MAXN=2e5+10;
struct node{long long a;char c;
}arr[MAXN];
int main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n;string str="";for(int i=1;i<=n;i++){cin>>arr[i].a>>arr[i].c;}for(int i=1;i<=n;i++){for(int j=1;j<=arr[i].a;j++){str+=arr[i].c;}}int cnt=0;int l=0,r=str.size()-1;while(l

然后。。。TLE了，68pts

把目光转向数据范围，字符串长度可达2×1e14

那么O(L)是极其不现实的，那么考虑O(n)

此时就要用到段级双指针

我们可以将回文检查的过程抽象为两个指针分别从字符串头部和尾部向中间移动。在普通字符串中，每次移动一步；但在 RLE 表示下，我们可以一次移动一整段（或一段的一部分）。

具体地，维护两个指针 \(l\) 和 \(r\)，分别指向当前未处理的最左段和最右段。同时维护这两段当前的剩余长度（因为可能只被部分消耗）。

每次迭代，我们考虑左段 \((a_l, c_l)\) 和右段 \((a_r, c_r)\) 的交集部分：

  • 令 \(t = \min(a_l, a_r)\)，这是左右两段当前能配对的长度。
  • 如果 \(c_l \neq c_r\)，那么这 \(t\) 对对称位置的字符都不同，每对需要修改一次，故答案增加 \(t\)。
  • 如果 \(c_l = c_r\)，这 \(t\) 对已经匹配，无需修改。

然后，将 \(a_l\) 和 \(a_r\) 都减去 \(t\)。若某段长度变为 0，说明该段已完全消耗，将对应指针向中间移动一位。

当 \(l > r\) 时，所有位置都已配对处理完毕；若 \(l == r\)，剩下的是正中间的一段，它自身关于中心对称，无需任何修改。

这个过程本质上是在模拟双指针从两端向中间扫描，但每次跳跃的长度是当前左右段的较小剩余长度，从而将 \(O(L)\) 的操作压缩到 \(O(n)\)。

上代码！！！

点击查看代码
#include
using namespace std;
int n;
const int MAXN=2e5+10;
struct node{long long a; // 段长度char c;      // 该段的字符
}arr[MAXN];
int main(){ios::sync_with_stdio(false); // 关闭同步流cin.tie(0);cout.tie(0);cin>>n;for(int i=1;i<=n;i++){cin>>arr[i].a>>arr[i].c;}long long ans=0; //十年OI一场空，不打_____ _____ 见祖宗 long long l=1,r=n;while(l