我是按照优先队列扩展的,WA了,想知道为什么不能这么做
#include<bits/stdc++.h>
#define int long long
using namespace std;
char s[2000010];
int mod=1e6+7;
int n;
vector<pair<int,int> >v[1000010];
struct node{
int l,r;
bool operator <(const node &cmp)const{
if(r-l!=cmp.r-cmp.l)
return r-l>cmp.r-cmp.l;
return l>cmp.l;
}
};
priority_queue<node>q;
int ql[2000010],qr[2000010];
int qwer(pair<int,int>x){
return (x.first*137%mod+x.second*1137%mod)%mod;
}
void push(pair<int,int>x){
v[qwer(x)].push_back(x);
}
int find(pair<int,int>x){
int h=qwer(x);
int len=v[h].size();
for(int i=0;i<len;i++){
if(v[h][i]==x){
return 1;
}
}
return 0;
}
void solve(){
int ans=0;
for(int i=1;i<n;i++){
if(s[i]==s[i+1]){
q.push({i,i+1});
qr[i]=i+1;
ql[i+1]=i;
}
}
while(!q.empty()){
node f=q.top();q.pop();
if(!find({f.l,f.r}))ans++;
else continue;
cout<<f.l<<' '<<f.r<<'\n';
push({f.l,f.r});
if(s[f.l-1]==s[f.r+1]&&f.l!=1&&f.r!=n){
q.push({f.l-1,f.r+1});
qr[f.l-1]=f.r+1;
ql[f.r+1]=f.l-1;
}
if(qr[f.r+1]&&f.r!=n){
q.push({f.l,qr[f.r+1]});
qr[f.l]=qr[f.r+1];
ql[qr[f.r+1]]=f.l;
}
if(ql[f.l-1]&&f.l!=1){
q.push({ql[f.l-1],f.r});
ql[f.r]=ql[f.l-1];
qr[ql[f.l-1]]=f.r;
}
}
cout<<ans;
}
signed main(){
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>s+1;
solve();
return 0;
}