E - Adnan and the Burned drivers
題目：
? 給出一個長度為1e5的字串，有1e5次操作，
? 操作1：修改一個字串里的某個字符，操作2：詢問字串的\([l, r]\)是否為回文子串，
思路：
? 對于一個字串快速判斷是否為回文串，可以用字串哈希通過判斷正反哈希值是否相等，在\(O(logn)\)的時間內解決該問題，但是本題有一個問題是帶修，那么我們可以考慮用資料結構來維護這個帶修的程序，查詢哈希值的程序就可以看做是一個區間求和問題，修改字符就是單點修改問題，要注意的是，要維護一個正方向的哈希值和一個反方向的哈希值，
實作：
? 關于字串哈希，用unsigned long long可以自動取模，基準數可以是131或者27，
? 在線段樹維護區間和的時候，需要注意左移和右移，
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
typedef unsigned long long ull;
char str[N];
ull bash[N * 4];
int n, m;
ull seg1[N * 4], seg2[N * 4];
void pushup(int k, int l, int r)
{
int mid = l + r >> 1;
seg1[k] = (seg1[k << 1] * bash[r - mid] + seg1[k << 1 | 1]);
seg2[k] = (seg2[k << 1] + seg2[k << 1 | 1] * bash[mid - l + 1]);
}
void update(int k, int l, int r, int x, int val)
{
if(l == r)
{
seg1[k] = seg2[k] = val;
return;
}
int mid = l + r >> 1;
if(x <= mid)
update(k << 1, l, mid, x, val);
else
update(k << 1 | 1, mid + 1, r, x, val);
pushup(k, l, r);
}
ull query(int k, int l, int r, int ql, int qr, int q)
{
if(ql == l && qr == r)
return q == 1 ? seg1[k] : seg2[k];
int mid = l + r >> 1;
if(qr <= mid)
return query(k << 1, l, mid, ql, qr, q);
else if(mid < ql)
return query(k << 1 | 1, mid + 1, r, ql, qr, q);
else if(q == 1)
return query(k << 1, l, mid, ql, mid, q) * bash[qr - mid] + query(k << 1 | 1, mid + 1, r, mid + 1, qr, q);
else
return query(k << 1, l, mid, ql, mid, q) + bash[mid - ql + 1] * query(k << 1 | 1, mid + 1, r, mid + 1, qr, q);
}
void init()
{
bash[0] = 1;
for(int i = 1; i <= 4e5; i ++)
bash[i] = bash[i - 1] * 131;
}
void solve()
{
memset(seg1, 0, sizeof seg1);
memset(seg2, 0, sizeof seg2);
scanf("%d%d", &n, &m);
scanf("%s", str + 1);
for(int i = 1; i <= n; i ++)
update(1, 1, n, i, str[i] - 'a');
while(m --)
{
int op, x, y;
scanf("%d%d", &op, &x);
if(op == 1)
{
char p[3];
scanf("%s", p);
update(1, 1, n, x, p[0] - 'a');
}
else
{
scanf("%d", &y);
if(x == y)
puts("Adnan Wins");
else
{
int mid = x + y >> 1;
ull q, p;
if((y - x + 1) & 1) //區間長度為奇數
q = query(1, 1, n, x, mid - 1, 0), p = query(1, 1, n, mid + 1, y, 1);
else //偶數
q = query(1, 1, n, x, mid, 0), p = query(1, 1, n, mid + 1, y, 1);
if(q == p)
puts("Adnan Wins");
else
puts("ARCNCD!");
}
}
}
}
int main()
{
init();
int _;
scanf("%d", &_);
while(_--)
solve();
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/507178.html
標籤：其他