/**
。∠(*・ω・)っ ⌒ 由 ~ (( ,,・з・,, ))
_Π_____。
/______/~\
| 田田|門|
> love miku so muchhhh <3
**/
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define el "\n"
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
//
struct Query
{
int t, x, y;
char c;
Query(int _t, int _x, int _y, char _c): t(_t), x(_x), y(_y), c(_c) {};
};
// var dec
const int maxn = 1e5 + 3;
const ll mod = 1e9 + 7;
int n, q;
string s;
// ds dec
vector <Query> queries;
//
namespace sub1
{
bool condition()
{
return (max(n, q) <= 15);
}
//
void solve()
{
vector <string> saved(q+1);
for (int z=0; z<q; ++z)
{
int t = queries[z].t, x = queries[z].x, y = queries[z].y;
char c = queries[z].c;
if (t == 1)
{
s[x] = c;
}
else if (t == 2)
{
int d = y-x+1;
int ans = 0;
for (int mask=0; mask<(1<<d); ++mask)
{
string temp = "";
int cnt = __builtin_popcount(mask);
if (cnt != 5) continue;
for (int j=0; j<d; ++j)
{
if (mask & (1<<j))
{
temp += s[x+j];
}
}
if (temp == "HSGQG") ans++;
}
cout << ans << el;
}
else
{
s = saved[x];
}
saved[z+1] = s;
}
}
}
//
namespace sub2
{
bool condition()
{
return (n <= 1000 && q == 1 && queries[0].t == 2 && queries[0].x == 1 && queries[0].y == n);
}
//
void solve()
{
string tdk = "HSGQG";
vector <vector<ll>> dp(5, vector<ll>(n+3, 0));
for (int i=1; i<=n; ++i)
{
for (int k=0; k<5; ++k)
{
int cnt = 0;
if (k == 0 && s[i] == tdk[k]) dp[k][i] = 1;
else if (s[i] == tdk[k])
{
for (int j=i-1; j>=1; --j)
{
if (s[j] == tdk[k-1])
{
dp[k][i] += dp[k-1][j];
if (dp[k][i] > mod) dp[k][i] -= mod;
}
}
}
}
}
// for (int k=0; k<5; ++k)
// {
// cout << k << ": ";
// for (int i=1; i<=n; ++i) cout << dp[k][i] << " ";
// cout << el;
// }
ll ans = 0;
for (int i=1; i<=n; ++i) (ans += dp[4][i]) %= mod;
cout << ans << el;
}
}
//
void solve()
{
cin >> n >> q;
cin >> s;
s = "#" + s;
for (int i=1; i<=q; ++i)
{
int t; cin >> t;
if (t == 1)
{
int x;
char c;
cin >> x >> c;
queries.pb(Query(1, x, -1, c));
}
else if (t == 2)
{
int x, y; cin >> x >> y;
queries.pb(Query(2, x, y, '0'));
}
else
{
int x; cin >> x;
queries.pb(Query(3, x, -1, '0'));
}
}
if (sub2::condition()) sub2::solve();
else sub1::solve();
}
//
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
if (fopen("hsgqg.inp", "r"))
{
freopen("hsgqg.inp", "r", stdin);
freopen("hsgqg.out", "w", stdout);
}
int t = 1;
// cin >> t;
while (t--) solve();
return 0;
}
Compilation message (stderr)
Main.cpp: In function 'int32_t main()':
Main.cpp:160:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
160 | freopen("hsgqg.inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:161:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
161 | freopen("hsgqg.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |