2022牛客寒假算法基础集训营4【解题报告】

戳我进入比赛

Problem A. R

题目大意

输入两个整数 $n,kn,k$ 和一个长度为 $nn$ 的字符串 $ss$.

问字符串 $ss$ 中存在多少个子串满足该子串至少包含 $kk$ 个 ${}^{\mathrm{\prime }}{R}^{\mathrm{\prime }}\text{'}R\text{'}$ 字符，且不包含 ${}^{\mathrm{\prime }}{P}^{\mathrm{\prime }}\text{'}P\text{'}$ 字符.

$1\le n\le 2\times 10^5,1\le k\le 20,s[i]\in {\{}^{\mathrm{\prime }}{A}^{\mathrm{\prime }}{-}^{\mathrm{\prime }}{Z}^{\mathrm{\prime }}\}1\; \backslash leq\; n\; \backslash leq\; 2\; \backslash times\; 10^5,\; 1\; \backslash leq\; k\; \backslash leq\; 20,\; s[i]\; \backslash in\; \backslash \{\text{'}A\text{'}-\text{'}Z\text{'}\backslash \}$.

分析

尺取或者二分都可以.

PS：赛时看到这种题总是不自觉地去写二分，大概因为我是二分大师吧（逃

代码

尺取

#include <bits/stdc++.h>
using namespace std;

template <typename T>
inline void scan(T& x) {
	x = 0; int f = 1; char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
	while(isdigit(ch))  {x = x * 10 + ch - '0', ch = getchar();}
	x *= f;
}

template <typename T>
void print(T x) {
	if(x < 0) putchar('-'), x = -x;
	if(x > 9) print(x / 10);
	putchar(x % 10 + '0');
}

template <typename T>
void print(T x, char ch) {
	print(x), putchar(ch);
}

typedef double db;
typedef long long ll;
typedef unsigned long long ull;

const db eps = 1e-6;
const int M = (int)2e5;
const int N = (int)1e5;
const ll mod = (ll)1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll linf = 0x3f3f3f3f3f3f3f3f;

int n, k;
char s[M + 5];
int suf[M + 5];

void work() {
	scan(n), scan(k);
	scanf("%s", s + 1);
	suf[n + 1] = n + 1; for(int i = n; i >= 1; --i) suf[i] = (s[i] == 'P' ? i : suf[i + 1]);
	ll ans = 0;
	for(int i = 1, pr = 0, cr = 0; i <= n; ++i) {
		while(pr + 1 <= n && cr < k) cr += (s[++pr] == 'R');
		if(cr == k && pr < suf[i]) ans += suf[i] - pr;
		if(s[i] == 'R') --cr;
	}
	print(ans, '\n');
}

int main() {
	/*ios::sync_with_stdio(0);
	  cin.tie(0); cout.tie(0);*/
//	freopen("in", "r", stdin);
//	freopen("out", "w", stdout);
	int T = 1; //scan(T);
	for(int ca = 1; ca <= T; ++ca) {
		work();
	}
//	cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
	return 0;
}

二分

#include <bits/stdc++.h>
using namespace std;

template <typename T>
inline void scan(T& x) {
	x = 0; int f = 1; char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
	while(isdigit(ch))  {x = x * 10 + ch - '0', ch = getchar();}
	x *= f;
}

template <typename T>
void print(T x) {
	if(x < 0) putchar('-'), x = -x;
	if(x > 9) print(x / 10);
	putchar(x % 10 + '0');
}

template <typename T>
void print(T x, char ch) {
	print(x), putchar(ch);
}

typedef double db;
typedef long long ll;
typedef unsigned long long ull;

const db eps = 1e-6;
const int M = (int)2e5;
const int N = (int)1e5;
const ll mod = (ll)1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll linf = 0x3f3f3f3f3f3f3f3f;

int n, k;
char s[M + 5];
int pre[2][M + 5];

bool check(int l, int r) {
    return pre[0][r] - pre[0][l - 1] >= k &&
           pre[1][r] - pre[1][l - 1] == 0;
}

int calL(int p) {
    int l = p, r = n + 1, mid;
    while(l < r) {
        mid = (l + r) >> 1;
        if(pre[0][mid] - pre[0][p - 1] >= k) r = mid;
        else l = mid + 1;
    }
    return r;
}

int calR(int p) {
    int l = p, r = n, mid;
    while(l < r) {
        mid = (l + r + 1) >> 1;
        if(pre[1][mid] - pre[1][p - 1] == 0) l = mid;
        else r = mid - 1;
    }
    return r;
}

int cal(int p) {
    int l = calL(p);
    if(l == n + 1 || pre[1][l] - pre[1][p - 1]) return 0;
    int r = calR(l);
    return r - l + 1;
}

void work() {
    scan(n), scan(k);
    scanf("%s", s + 1);
    for(int i = 1; i <= n; ++i) {
        pre[0][i] = pre[0][i - 1] + (s[i] == 'R');
        pre[1][i] = pre[1][i - 1] + (s[i] == 'P');
    }
    ll ans = 0;
    for(int i = 1; i <= n; ++i) {
        ans += cal(i);
    }
    print(ans, '\n');
}

int main() {
	/*ios::sync_with_stdio(0);
	  cin.tie(0); cout.tie(0);*/
//	freopen("in", "r", stdin);
//	freopen("out", "w", stdout);
	int T = 1; //scan(T);
	for(int ca = 1; ca <= T; ++ca) {
		work();
	}
//	cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
	return 0;
}

Problem B. 进制

题目大意

输入两个整数 $n,qn,\; q$ 和一个长度为 $nn$ 的字符串 $ss$.

接下来 $qq$ 次操作，每行输入 $op,x,yop,\; x,\; y$.

若 $op=1op=1$ 则表示令 $s_x=y(1\le x\le n,0\le y\le 9)s\_x=y\; \backslash ,\; (1\; \backslash leq\; x\; \backslash leq\; n,\; 0\; \backslash leq\; y\; \backslash leq\; 9)$.

否则若 $op=2op=2$ 则表示查询区间 $[x,y](1\le x\le y\le n)[x,y]\; \backslash ,\; (1\; \backslash leq\; x\; \backslash leq\; y\; \backslash leq\; n)$，该区间子串所能表示的某进制的最小值（进制必须合法，且必须是二进制到十进制之间，可以包含前导零），对 $10^9+710^9+7$ 取模.

$1\le n,q\le 10^5,s[i]\in \{0-9\}1\; \backslash leq\; n,q\; \backslash leq\; 10^5,s[i]\; \backslash in\; \backslash \{0-9\backslash \}$.

分析

显然对于查询操作，进制应该选为区间 $[x,y][x,y]$ 的最大值+1.

用线段树维护区间最小值和字符串 $ss$ 在 $2-102-10$ 进制表示下的数，查询时即区间求和，再在对应进制下移位即可.

比如查询到的值为 $s[x]b^{l+x-y}+\cdots +s[y+1]b^{l+1}+s[y]b^{l}s[x]\; b^\{l+x-y\}\; +\; \backslash cdots\; +s[y+1]b^\{l+1\}+s[y]b^l$，记为 $qq$，那么答案即为 $\frac{q}{b^l}\backslash frac\{q\}\{b^l\}$.

代码

#include <bits/stdc++.h>
using namespace std;

template <typename T>
inline void scan(T& x) {
	x = 0; int f = 1; char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
	while(isdigit(ch))  {x = x * 10 + ch - '0', ch = getchar();}
	x *= f;
}

template <typename T>
void print(T x) {
	if(x < 0) putchar('-'), x = -x;
	if(x > 9) print(x / 10);
	putchar(x % 10 + '0');
}

template <typename T>
void print(T x, char ch) {
	print(x), putchar(ch);
}

typedef double db;
typedef long long ll;
typedef unsigned long long ull;

const db eps = 1e-6;
const int M = (int)1e5;
const int N = (int)1e5;
const ll mod = (ll)1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll linf = 0x3f3f3f3f3f3f3f3f;

ll quick(ll a, ll b, ll p = mod)
{
    ll s = 1;
    while(b)
    {
        if(b & 1) s = s * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return s % p;
}

ll inv(ll n, ll p = mod)
{
    return quick(n, p - 2, p);
}

int n, q;
char s[M + 5];

struct segT {
    int mx[M * 4 + 5];
    int w[M * 4 + 5][11];

    int lc(int k) {return k<<1;}
    int rc(int k) {return k<<1|1;}

    void push_up(int k) {
        mx[k] = max(mx[lc(k)], mx[rc(k)]);
        for(int i = 2; i <= 10; ++i) w[k][i] = (w[lc(k)][i] + w[rc(k)][i]) % mod;
    }

    void nmsl() {
        printf("-----------------------\n");
        for(int i = 1; i <= 9; ++i) {
            printf("%d: mx=%d w4=%d\n", i, mx[i], w[i][4]);
        }
        printf("---------------------\n");
    }

    void build(int k, int l, int r) {
        if(l == r) {
            mx[k] = s[l] - '0';
            for(int i = 2; i <= 10; ++i) w[k][i] = (ll)mx[k] * quick(i, n - l) % mod;
            return;
        }
        int mid = (l + r) >> 1;
        build(lc(k), l, mid);
        build(rc(k), mid + 1, r);
        push_up(k);
    }

    void update(int k, int l, int r, int a, int b) {
        if(l == r) {
            mx[k] = b;
            for(int i = 2; i <= 10; ++i) w[k][i] = (ll)mx[k] * quick(i, n - l) % mod;
            return;
        }
        int mid = (l + r) >> 1;
        if(a <= mid) update(lc(k), l, mid, a, b);
        else update(rc(k), mid + 1, r, a, b);
        push_up(k);
    }

    int queryMx(int k, int l, int r, int a, int b) {
        if(l >= a && r <= b) return mx[k];
        int mid = (l + r) >>1, mx = 0;
        if(a <= mid) mx = max(mx, queryMx(lc(k), l, mid, a, b));
        if(mid < b)  mx = max(mx, queryMx(rc(k), mid + 1, r, a, b));
        return mx;
    }

    int query(int k, int l, int r, int a, int b, int c) {
        if(l >= a && r <= b) return w[k][c];
        int mid = (l + r) >>1, sum = 0;
        if(a <= mid) (sum += query(lc(k), l, mid, a, b, c)) %= mod;
        if(mid < b)  (sum += query(rc(k), mid + 1, r, a, b, c)) %= mod;
        return sum;
    }
} tr;

/**

5 5
56789
1 3 3
1 1 8
2 2 5
2 5 5
2 1 1

6389
9
8
**/

void work() {
    scan(n), scan(q);
    scanf("%s", s + 1);
    tr.build(1, 1, n);
    for(int i = 1, op, x, y; i <= q; ++i) {
        scan(op), scan(x), scan(y);
        if(op == 1) tr.update(1, 1, n, x, y);
        else {
            int bs = max(2, tr.queryMx(1, 1, n, x, y) + 1);
            int pro = tr.query(1, 1, n, x, y, bs);
            int ans = (ll)pro * inv(quick(bs, n - y)) % mod;
            print(ans, '\n');
        }
    }
}

int main() {
	/*ios::sync_with_stdio(0);
	  cin.tie(0); cout.tie(0);*/
//	freopen("in", "r", stdin);
//	freopen("out", "w", stdout);
	int T = 1; //scan(T);
	for(int ca = 1; ca <= T; ++ca) {
		work();
	}
//	cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
	return 0;
}

Problem C. 蓝彗星

题目大意

输入两个正整数 $nn$ 和 $tt$，表示有 $nn$ 颗彗星，第 $ii$ 颗彗星的颜色为 $s[i]s[i]$，开始时刻为 $a[i]a[i]$，持续时间为 $tt$.

问有多少个单位时间可以观察到蓝彗星且看不到红彗星.

$1\le n,t,a[i]\le 10^5,s[i]\in {\{}^{\mathrm{\prime }}{B}^{\mathrm{\prime }}{,}^{\mathrm{\prime }}{R}^{\mathrm{\prime }}\}1\; \backslash leq\; n,t,a[i]\; \backslash leq\; 10^5,\; s[i]\; \backslash in\; \backslash \{\text{'}B\text{'},\text{'}R\text{'}\backslash \}$.

分析

直接模拟就行了，枚举当前时间，维护红蓝彗星的个数.

代码

#include <bits/stdc++.h>
using namespace std;

template <typename T>
inline void scan(T& x) {
	x = 0; int f = 1; char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
	while(isdigit(ch))  {x = x * 10 + ch - '0', ch = getchar();}
	x *= f;
}

template <typename T>
void print(T x) {
	if(x < 0) putchar('-'), x = -x;
	if(x > 9) print(x / 10);
	putchar(x % 10 + '0');
}

template <typename T>
void print(T x, char ch) {
	print(x), putchar(ch);
}

typedef double db;
typedef long long ll;
typedef unsigned long long ull;

const db eps = 1e-6;
const int M = (int)1e5;
const int N = (int)1e5;
const ll mod = (ll)1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll linf = 0x3f3f3f3f3f3f3f3f;

int n, t;
char s[M + 5];
int a[M + 5];
int id[M + 5];

struct qnode {
    int en; char ch;
    qnode(int _en, char _ch): en(_en), ch(_ch){}
    bool operator<(const qnode& b) const {
        return en > b.en;
    }
};
priority_queue<qnode> q;

void work() {
    scan(n), scan(t);
    scanf("%s", s + 1);
    for(int i = 1; i <= n; ++i) scan(a[i]), id[i] = i;
    sort(id + 1, id + n + 1, [&](int x, int y) {
         return a[x] < a[y];
    });
    int bc = 0, rc = 0, ans = 0;
    for(int i = 1, j = 1; i <= 2 * M; ++i) {
        while(!q.empty() && q.top().en == i) {
            if(q.top().ch == 'B') --bc;
            else --rc;
            q.pop();
        }
        while(j <= n && a[id[j]] == i) {
            if(s[id[j]] == 'B') ++bc;
            else ++rc;
            q.push(qnode(a[id[j]] + t, s[id[j]]));
            ++j;
        }
        if(bc && !rc) ++ans;
    }
    print(ans, '\n');
}

int main() {
	/*ios::sync_with_stdio(0);
	  cin.tie(0); cout.tie(0);*/
//	freopen("in", "r", stdin);
//	freopen("out", "w", stdout);
	int T = 1; //scan(T);
	for(int ca = 1; ca <= T; ++ca) {
		work();
	}
//	cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
	return 0;
}

Problem D. 雪色光晕

题目大意

有一个动点 $(x_0,y_0)(x\_0,y\_0)$ 和一个不动点 $(x,y)(x,y)$，接下来 $nn$ 个单位时间，每个单位时间该动点会从当前位置 $(x0,y0)(x0,y0)$ 移动到 $(x_0+x_i,y_0+y_i)(x\_0+x\_i,y\_0+y\_i)$.

问过程中动点与不动点的最短距离.

$1\le n\le 2\times 10^5,-10^9\le x_i,y_i\le 10^{9}1\; \backslash leq\; n\; \backslash leq\; 2\; \backslash times\; 10^5,\; -10^9\; \backslash leq\; x\_i,y\_i\; \backslash leq\; 10^9$.

分析

其实就是求点到线段距离，板子一套就完事~

代码

#include <bits/stdc++.h>
using namespace std;

template <typename T>
inline void scan(T& x) {
	x = 0; int f = 1; char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
	while(isdigit(ch))  {x = x * 10 + ch - '0', ch = getchar();}
	x *= f;
}

template <typename T>
void print(T x) {
	if(x < 0) putchar('-'), x = -x;
	if(x > 9) print(x / 10);
	putchar(x % 10 + '0');
}

template <typename T>
void print(T x, char ch) {
	print(x), putchar(ch);
}

typedef double db;
typedef long long ll;
typedef unsigned long long ull;

namespace Geo {
    typedef double db;
    const db eps = 1e-9, PI = acos(-1), inf = numeric_limits<db>::max();
    inline int sign(db a) {return a < -eps ? -1 : a > eps;}
    inline int cmp(db a, db b) {return sign(a - b);}
    inline bool inmid(db k, db a, db b) {return sign(a - k) * sign(b - k) <= 0;}
    struct Point {
        db x, y;
        Point(db _x, db _y): x(_x), y(_y){}
        Point() = default;
        Point operator+(const Point& b) const {return Point(x + b.x, y + b.y);}
        Point operator-(const Point& b) const {return Point(x - b.x, y - b.y);}
        Point operator*(const db& b) const {return Point(x * b, y * b);}
        Point operator/(const db& b) const {return Point(x / b, y / b);}
        bool operator==(const Point& b) const {return !cmp(x, b.x) && !cmp(y, b.y);}
        bool operator!=(const Point& b) const {return !(*this == b);}
        bool operator<(const Point& b) const {
            int c = cmp(x, b.x);
            if(c) return c == -1;
            return cmp(y, b.y) == -1;
        }
        bool operator>(const Point& b) const {return b < *this;}
        Point right(const db& len) {return Point(x + len, y);}
        Point up(const db& len) {return Point(x, y + len);}
        db length() const {return hypot(x, y);}
        db length2() const {return x * x +  y * y;}
        Point unit() const {return *this / this->length();}
        void print() const {printf("%.11f %.11f\n", x, y);}
        void scan() const {scanf("%lf %lf", &x, &y);}
        db dis(Point b) const {return (*this - b).length();}
        db dis2(Point b) const {return (*this - b).length2();}
        Point rotate(db ac) const {return Point(x * cos(ac) - y * sin(ac), y * cos(ac) + x * sin(ac));}
        Point rotate90() const {return Point(-y, x);}
        db dot(Point o) const {return x * o.x + y * o.y;}
        db det(Point o) const {return x * o.y - y * o.x;}
    };
    typedef Point Vector;
    typedef vector<Point> Polygon;
    struct Line {
        Point u, v;
        Line(const Point& _a, const Point& _b): u(_a), v(_b){}
        Line() = default;
        Vector getVec() const {return v - u;}
        Line go(Vector t) {return Line(u + t, v + t);}
        bool isPoint() const {return u == v;}
        db length() const {return u.dis(v);}
        db length2() const {return u.dis2(v);}
        void print() const {u.print(), v.print();}
        void scan() {u.scan(), v.scan();}
    };
    inline db dot(Point ab, Point ac) { //点积
        return ab.x * ac.x + ab.y * ac.y;
    } //|ab|*|ac|*cosa
    inline int dotOp(Point c, Point a = {0, 0}, Point b = {0, 1e5}) {
        return sign(dot(b - a, c - a));
    } //+: 1,4  -: 2,3
    inline db cross(Point ab, Point ac) { //叉积
        return ab.x * ac.y - ab.y * ac.x;
    } //|ab|*|ac|*sina
    inline int crossOp(Point c, Point a = {0, 0}, Point b = {0, 1e5}) {
        return sign(cross(b - a, c - a));
    } //+: 1,2  -: 3,4
    inline int Op(Point c, Point a = {0, 0}, Point b = {0, 1e5}) { //相对象限
        int lr = dotOp(c, a, b), ud = crossOp(c, a, b);
        if(!lr || !ud) return 0;
        return lr + ud == 2 ? 1 : (lr + ud == -2 ? 3 : (lr == -1 ? 2 : 4));
    }
    inline int Quadrant(const Point& a) { //象限
        int x = cmp(a.x, 0), y = cmp(a.y, 0);
        if(x > 0 && y > 0) return 1;
        if(x < 0 && y > 0) return 2;
        if(x < 0 && y < 0) return 3;
        if(x > 0 && y < 0) return 4;
        return 0;
    }
    bool parallel(const Line& a, const Line& b) { //直线平行
        return sign(cross(a.getVec(), b.getVec())) == 0;
    }
    bool sameDir(const Line& a, const Line& b) { //直线同向
        return parallel(a, b) && sign(dot(a.getVec(), b.getVec())) == 1;
    }
    bool vertical(const Line& a, const Line& b) { // 直线垂直
        return sign(dot(a.getVec(), b.getVec())) == 0;
    }
//    bool compairAng(const Point& a, const Point& b) {
//    }
//    bool operator<(const Line& a, const Line& b) {
//    }
    inline db disPtoL(Point c, Line a) { //点到直线距离
        return fabs(cross(a.getVec(), c - a.u)) / a.length();
    }
    inline Point nearestPoint(Point c, Line ab) { //点到线段的最近点
        db t = dot(c - ab.u, ab.getVec()) / ab.length2();
        if(0 <= t && t <= 1) return ab.u + ab.getVec() * t;
        return c.dis(ab.u) > c.dis(ab.v) ? ab.v : ab.u;
    }
    inline db disPtol(Point c, Line a) { //点到线段距离
        return c.dis(nearestPoint(c, a));
    }
    inline Point pjPoint(Point c, Point a, Point b) { //投影点
        return a + (b - a).unit() * dot(c - a, b - a) / (b - a).length();
    }
    inline Point symPoint(Point c, Point a, Point b) { //对称点
        return pjPoint(c, a, b) * 2 - c;
    }
    inline Point getInsec(Point a, Point b, Point c, Point d) { //获取交点
        db w1 = cross(a - c, d - c), w2 = cross(d - c, b - c);
        return (a * w2 + b * w1) / (w1 + w2);
    }
    inline Point getInsec(Line a, Line b) { //直线交点
        return getInsec(a.u, a.v, b.u, b.v);
    }
    inline bool inseg(Point c, Point a, Point b) { //点在线段上
        if(c == a || c == b) return 1;
        return sign(cross(b - a, c - a)) == 0 && sign(dot(a - c, b - c)) == -1;
    }
    inline bool inseg(Point c, Line ab) { //点在线段上
        return inseg(c, ab.u, ab.v);
    }
    inline bool intersect(db l1, db r1, db l2, db r2) { //排斥实验 检查线段对角线矩形是否相交
        if(l1 > r1) swap(l1, r1);
        if(l2 > r2) swap(l2, r2);
        return cmp(r2, l1) != -1 && cmp(r1, l2) != -1;
    }
    inline int spanLine(Point a, Point b, Point c, Point d) { //线段ab跨立线段cd 跨立试验 <0成功 =0在直线上 >0失败
        return sign(cross(a - c, d - c)) * sign(cross(b - c, d - c));
    }
    inline int spanLine(Line a, Line b) { //线段a跨立线段b 跨立试验 <0成功 =0在直线上 >0失败
        return spanLine(a.u, a.v, b.u, b.v);
    }
    inline bool checkSSsp(Point a, Point b, Point c, Point d) { //线段严格相交
        return spanLine(a, b, c, d) < 0 && spanLine(c, d, a, b) < 0;
    }
    inline bool checkSS(Point a, Point b, Point c, Point d) { //线段非严格相交
        return intersect(a.x, b.x, c.x, d.x) && intersect(a.y, b.y, c.y, d.y)
            && spanLine(a, b, c, d) <= 0 && spanLine(c, d, a, b) <= 0;
    }
    inline bool checkSS(Line a, Line b, bool Notsp = true) {
        if(Notsp) return checkSS(a.u, a.v, b.u, b.v);
        else      return checkSSsp(a.u, a.v, b.u, b.v);
    }
    inline db disltol(Line a, Line b) { //线段到线段距离
        if(checkSS(a, b, 1)) return 0;
        return min(min(disPtol(a.u, b), disPtol(a.v, b)),
                   min(disPtol(b.u, a), disPtol(b.v, a)));
    }
    inline bool cmpAtan(Point a, Point b) { //极角排序
        if(cmp(atan2(a.y, a.x), atan2(b.y, b.x)) != 0) return atan2(a.y, a.x) < atan2(b.y, b.x);
        return a.x < b.x;
    }
    inline void sortACW(Polygon& v) { //逆时针排序
        Point g(0, 0);
        int n = v.size();
        for(int i = 0; i < n; ++i) g.x += v[i].x, g.y += v[i].y;
        g.x /= n, g.y /= n;
        sort(v.begin(), v.end(), [&](Point& a, Point& b) {return sign(cross(a - g, b - g)) == 1;});
    }
    inline db area(const Polygon& v) { //多边形面积 需要逆时针排序
        db ans = 0;
        int len = v.size();
        if(len < 3) return 0;
        for(int i = 0; i < len; ++i) ans += cross(v[i], v[(i + 1) % len]);
        return ans / 2;
    }
    inline bool isConvex(const Polygon& v) { //判断凸多边形 需要逆时针排序
        int n = v.size();
        if(n < 3) return 0;
        for(int i = 0; i < n; ++i) {
            if(cross(v[(i + 1) % n] - v[i], v[(i + 2) % n] - v[(i + 1) % n]) < 0) return 0;
        }
        return 1;
    }
    inline int contain(const Polygon& v, Point q) { //点和多边形位置关系 内部1 外部-1 多边形上0
        int n = v.size();
        int res = -1;
        for(int i = 0; i < n; ++i) {
            Vector a = v[i] - q, b = v[(i + 1) % n] - q;
            if(cmp(a.y, b.y) == 1) swap(a, b);
            if(sign(a.y) != 1 && sign(b.y) == 1 && sign(cross(a, b)) == 1) res = -res;
            if(sign(cross(a, b)) == 0 && sign(dot(a, b)) != 1) return 0;
        }
        return res;
    }
    inline Polygon ConvexHull(Polygon A, int flag = 1) { //凸包 不严格0 严格1
        int n = A.size();
        if(n <= 2) return A;
        Polygon ans(n * 2);
        int now = -1;
        sort(A.begin(), A.end());
        for(int i = 0; i < n; ans[++now] = A[i++])
            while(now > 0 && crossOp(A[i], ans[now - 1], ans[now]) < flag) --now;
        for(int i = n - 2, pre = now; i >= 0; ans[++now] = A[i--])
            while(now > pre && crossOp(A[i], ans[now - 1], ans[now]) < flag) --now;
        ans.resize(now);
        return ans;
    }
    inline db convexDimater(Polygon v) { //凸包直径
        int now = 0, n = v.size();
        db ans = 0;
        for(int i = 0; i < n; ++i) {
            now = max(now, i);
            while(1) {
                db k1 = v[i].dis(v[now % n]), k2 = v[i].dis(v[(now + 1) % n]);
                ans = max(ans, max(k1, k2));
                if(cmp(k2, k1) == 1) ++now;
                else                 break;
            }
        }
        return ans;
    }
    inline Polygon convexCut(Polygon v, Line a) { //凸包v被直线a分割成的逆时针凸包
        int n = v.size();
        Polygon ans;
        for(int i = 0; i < n; ++i) {
            int k1 = crossOp(v[i], a.u, a.v), k2 = crossOp(v[(i + 1) % n], a.u, a.v);
            if(k1 >= 0) ans.emplace_back(v[i]);
            if(k1 * k2 < 0) ans.emplace_back(getInsec(a, Line(v[i], v[(i + 1) % n])));
        }
        return ans;
    }
    db NPPD(int l, int r, const vector<Point>& v, vector<int>& tmp) {
        if(l == r) return inf;
        if(l + 1 == r) return v[l].dis(v[r]);
        int mid = (l + r) >> 1;
        db d = min(NPPD(l, mid, v, tmp), NPPD(mid + 1, r, v, tmp));
        int p = 0;
        for(int i = l; i <= r; ++i) if(fabs(v[mid].x - v[i].x) < d) tmp[p++] = i;
        sort(tmp.begin(), tmp.begin() + p, [&](int& a, int& b){return cmp(v[a].y, v[b].y) == -1;});
        for(int i = 0; i < p; ++i) {
            for(int j = i + 1; j < p && v[tmp[j]].y - v[tmp[i]].y < d; ++j) {
                d = min(d, v[tmp[j]].dis(v[tmp[i]]));
            }
        }
        return d;
    }
    db nearestPPDis(vector<Point> v) {//平面最近点对
        sort(v.begin(), v.end());
        int n = v.size();
        vector<int> tmp(n);
        return NPPD(0, n - 1, v, tmp);
    }
    struct Circle {
        Point o;
        db r;
        void scan() {
            o.scan();
            scanf("%lf", &r);
        }
        Circle(Point _o, db _r): o(_o), r(_r){}
        Circle() = default;
        bool operator==(const Circle b) const {
            return o == b.o && cmp(r, b.r) == 0;
        }
        db area() {return PI * r * r;}
        int contain(Point t) { //1圆外 0圆上 -1圆内
            return cmp(o.dis(t), r);
        }
        bool intersect(Circle b) {//两圆是否相交
            return cmp(o.dis(o), r + b.r) != 1
                && cmp(o.dis(o), fabs(r - b.r)) != -1;
        }
        int posRela(Circle b) {//0外离 1外切 2相交 3内切 4内含
            db d = o.dis(b.o);
            if(cmp(d, r + b.r) == 1) return 0;
            if(cmp(d, r + b.r) == 0) return 1;
            if(cmp(d, r + b.r) == -1 && cmp(d, fabs(r - b.r)) == 1) return 2;
            if(cmp(d, fabs(r - b.r)) == 0) return 3;
            if(cmp(d, fabs(r - b.r)) == -1) return 4;
            assert(0);
        }
        int intersect(Line t) { //-1相交 0相切 1相离
            return cmp(disPtoL(o, t), r);
        }
        int intersect_seg(Line t) {
            Point k = nearestPoint(o, t);
            return cmp(o.dis(k), r);
        }
    };
}

typedef Geo::Point point;
typedef Geo::Line line;
typedef Geo::Polygon polygon;
typedef Geo::Circle circle;
function<int(db)> sign = Geo::sign;
function<int(db, db)> cmp = Geo::cmp;

const db eps = 1e-6;
const int M = (int)2e5;
const int N = (int)1e5;
const ll mod = (ll)1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll linf = 0x3f3f3f3f3f3f3f3f;

int n;
point p[M + 5];

void work() {
    scan(n);
    for(int i = 0; i <= n + 1; ++i) p[i].scan();
    db mi = (ll)1e18;
    swap(p[0], p[1]);
    for(int i = 1; i <= n; ++i) {
        mi = min(mi,
                 disPtol(p[0],
                         line(p[1], p[1] + p[i + 1])));
        p[1] = p[1] + p[i + 1];
    }
    printf("%.12f\n", mi);
}

int main() {
	/*ios::sync_with_stdio(0);
	  cin.tie(0); cout.tie(0);*/
//	freopen("in", "r", stdin);
//	freopen("out", "w", stdout);
	int T = 1; //scan(T);
	for(int ca = 1; ca <= T; ++ca) {
		work();
	}
//	cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
	return 0;
}

Problem E. 真假签到题

题目大意

给了一份代码：

long long f(long long x){
    if(x==1)return 1;
    return f(x/2)+f(x/2+x%2);
}

给出正整数 $xx$，求 $f(x)f(x)$.

$1\le x\le 10^{18}1\; \backslash leq\; x\; \backslash leq\; 10^\{18\}$.

分析

直接跑一下前几项，可以发现 $f(x)=xf(x)=x$.

代码

print(input())

Problem F. 小红的记谱法

题目大意

大模拟，懒得写的了...

分析

摸摸摸%%%

代码

#include <bits/stdc++.h>
using namespace std;

template <typename T>
inline void scan(T& x) {
	x = 0; int f = 1; char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
	while(isdigit(ch))  {x = x * 10 + ch - '0', ch = getchar();}
	x *= f;
}

template <typename T>
void print(T x) {
	if(x < 0) putchar('-'), x = -x;
	if(x > 9) print(x / 10);
	putchar(x % 10 + '0');
}

template <typename T>
void print(T x, char ch) {
	print(x), putchar(ch);
}

typedef double db;
typedef long long ll;
typedef unsigned long long ull;

const db eps = 1e-6;
const int M = (int)1e5;
const int N = (int)1e5;
const ll mod = (ll)1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll linf = 0x3f3f3f3f3f3f3f3f;

int getID(char ch) {
    if(ch == 'C') return 1;
    if(ch == 'D') return 2;
    if(ch == 'E') return 3;
    if(ch == 'F') return 4;
    if(ch == 'G') return 5;
    if(ch == 'A') return 6;
    if(ch == 'B') return 7;
    assert(0);
}

char s[M + 5];
vector<pair<int, int>> num;

void work() {
    scanf("%s", s + 1);
    int n = strlen(s + 1);
    for(int i = 1, j = 0; i <= n; ++i) {
        if(s[i] == '<') --j;
        else if(s[i] == '>') ++j;
        else num.push_back(make_pair(getID(s[i]), j));
    }
    for(auto [a, b]: num) {
        print(a);
        while(b < 0) putchar('.'), ++b;
        while(b > 0) putchar('*'), --b;
    }
    putchar('\n');
}

int main() {
	/*ios::sync_with_stdio(0);
	  cin.tie(0); cout.tie(0);*/
//	freopen("in", "r", stdin);
//	freopen("out", "w", stdout);
	int T = 1; //scan(T);
	for(int ca = 1; ca <= T; ++ca) {
		work();
	}
//	cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
	return 0;
}

Problem G. 子序列权值乘积

题目大意

给一个长度为 $nn$ 的序列 $aa$，求序列 $aa$ 所有子序列的最大值与最小值乘积的乘积，答案对 $10^9+710^9+7$ 取模.

$1\le n\le 2\times 10^5,1\le a[i]\le 10^{9}1\; \backslash leq\; n\; \backslash leq\; 2\; \backslash times\; 10^5,\; 1\; \backslash leq\; a[i]\; \backslash leq\; 10^9$.

分析

显然，对序列 $aa$ 排个序对答案是不影响的. 由于求的是所有子序列的最大值与最小值乘积的乘积，所以我们可以单独考虑最大值与最小值的贡献，下面以求最大值为例，最小值同理.

枚举 $ii$，表示 $a[i]a[i]$ 为最大值，那么 $ii$ 必选，$[i+1,n][i+1,n]$ 必不能选，$[1,i-1][1,i-1]$ 可选可不选. 因此共有 $2^{i-1}2^\{i-1\}$ 种方案，$a[i]a[i]$ 作为最大值的贡献即为 $a[i{]}^{2^{i-1}}a[i]^\{2^\{i-1\}\}$.

由于 $2^{i-1}2^\{i-1\}$ 很大，不可能先把 $2^{i-1}2^\{i-1\}$ 求出来再快速幂求 $a[i{]}^{2^{i-1}}a[i]^\{2^\{i-1\}\}$，所以就该欧拉降幂登场啦~

因为 $a[i]a[i]$ 与 $10^9+710^9+7$ 互质，所以 $a[i{]}^{2^{i-1}}\mathrm{\%}(10^9+7)=a[i{]}^{2^{i-1}\mathrm{\%}\phi (10^9+7)}\mathrm{\%}(10^9+7)a[i]^\{2^\{i-1\}\}\; \backslash \%\; (10^9+7)\; =\; a[i]^\{2^\{i-1\}\backslash \%\backslash varphi(10^9+7)\}\; \backslash \%\; (10^9+7)$.

就完啦，就完啦，就完啦~~

代码

#include <bits/stdc++.h>
using namespace std;

template <typename T>
inline void scan(T& x) {
	x = 0; int f = 1; char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
	while(isdigit(ch))  {x = x * 10 + ch - '0', ch = getchar();}
	x *= f;
}

template <typename T>
void print(T x) {
	if(x < 0) putchar('-'), x = -x;
	if(x > 9) print(x / 10);
	putchar(x % 10 + '0');
}

template <typename T>
void print(T x, char ch) {
	print(x), putchar(ch);
}

typedef double db;
typedef long long ll;
typedef unsigned long long ull;

const db eps = 1e-6;
const int M = (int)2e5;
const int N = (int)1e5;
const ll mod = (ll)1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll linf = 0x3f3f3f3f3f3f3f3f;

int n;
int a[M + 5];

ll quick(ll a, ll b, ll p = mod)
{
    ll s = 1;
    while(b)
    {
        if(b & 1) s = s * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return s % p;
}

void work() {
    scan(n);
    for(int i = 1; i <= n; ++i) scan(a[i]);
    sort(a + 1, a + n + 1);
    int ans = 1;
    for(int i = 1; i <= n; ++i) ans = (ll)ans * quick(a[i], quick(2, i - 1, mod - 1)) % mod;
    for(int i = 1; i <= n; ++i) ans = (ll)ans * quick(a[i], quick(2, n - i, mod - 1)) % mod;
    print(ans, '\n');
}

int main() {
	/*ios::sync_with_stdio(0);
	  cin.tie(0); cout.tie(0);*/
//	freopen("in", "r", stdin);
//	freopen("out", "w", stdout);
	int T = 1; //scan(T);
	for(int ca = 1; ca <= T; ++ca) {
		work();
	}
//	cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
	return 0;
}

Problem H. 真真真真真签到题

题目大意

有一个正方体，A 先在正方体内选一个位置，B 再在正方体内选一个位置，A 希望离 B 尽可能近，B 希望离 A 尽可能远.

已知 A 与 B 的距离为 $xx$，求正方体的体积.

分析

很明显，这题可以推柿子（但正经人谁推柿子啊

显然啊，$x^{3}x^3$ 与 答案一定成常数倍关系，那么把样例算一算，常数倍数就得到了（偷笑

代码

#include <bits/stdc++.h>
using namespace std;

template <typename T>
inline void scan(T& x)
{
    x = 0; int f = 1; char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
    while(isdigit(ch))  {x = x * 10 + ch - '0', ch = getchar();}
    x *= f;
}

template <typename T>
void print(T x)
{
    if(x < 0) putchar('-'), x = -x;
    if(x > 9) print(x / 10);
    putchar(x % 10 + '0');
}

template <typename T>
void print(T x, char ch)
{
    print(x), putchar(ch);
}

typedef double db;
typedef long long ll;

const int M = (int)1e5;
const int N = (int)1e5;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)1e9 + 7;

void work()
{
    int x; scan(x);
    printf("%.12f\n", x * x * x * 1.5396007178425125170687300864816);
}

int main()
{
//    ios::sync_with_stdio(0);
//    cin.tie(0); cout.tie(0);
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//    int T; read(T);
//    for(int ca = 1; ca <= T; ++ca)
//    {
//        work();
//    }
    work();
//    cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
    return 0;
}

Problem I. 爆炸的符卡洋洋洒洒

题目大意

有 $nn$ 个物品，每个物品有两种属性，$a_{i}a\_i$ 表示消耗，$b_{i}b\_i$ 表示威力.

一组物品的消耗为该组物品消耗之和，威力为改组物品威力之和.

问选一组物品，在消耗为 $kk$ 的倍数的条件下，威力最大值是多少.

$1\le n,k\le 10^3,1\le a_i,b_i\le 10^{9}1\; \backslash leq\; n,k\; \backslash leq\; 10^3,\; 1\; \backslash leq\; a\_i,b\_i\; \backslash leq\; 10^9$.

分析

分析啥，这不就无脑dp么

代码

#include <bits/stdc++.h>
using namespace std;

template <typename T>
inline void scan(T& x) {
	x = 0; int f = 1; char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
	while(isdigit(ch))  {x = x * 10 + ch - '0', ch = getchar();}
	x *= f;
}

template <typename T>
void print(T x) {
	if(x < 0) putchar('-'), x = -x;
	if(x > 9) print(x / 10);
	putchar(x % 10 + '0');
}

template <typename T>
void print(T x, char ch) {
	print(x), putchar(ch);
}

typedef double db;
typedef long long ll;
typedef unsigned long long ull;

const db eps = 1e-6;
const int M = (int)1e3;
const int N = (int)1e5;
const ll mod = (ll)1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll linf = 0x3f3f3f3f3f3f3f3f;

int n, k;
ll f[M + 5][M + 5];

void work() {
    scan(n), scan(k);
    memset(f, -0x3f, sizeof f);
    f[0][0] = 0;
    for(int i = 1, a, b; i <= n; ++i) {
        scan(a), scan(b);
        for(int j = 0; j < k; ++j) {
            f[i][j] = f[i - 1][j];
            f[i][j] = max(f[i][j], f[i - 1][(j - a % k + k) % k] + b);
        }
    }
    if(f[n][0] <= 0) print(-1, '\n');
    else print(f[n][0], '\n');
}

int main() {
	/*ios::sync_with_stdio(0);
	  cin.tie(0); cout.tie(0);*/
//	freopen("in", "r", stdin);
//	freopen("out", "w", stdout);
	int T = 1; //scan(T);
	for(int ca = 1; ca <= T; ++ca) {
		work();
	}
//	cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
	return 0;
}

Problem J. 区间合数的最小公倍数

题目大意

给出 $l,rl,r$，问区间 $[l,r][l,r]$ 所有合数的 lcm，答案对 $10^9+710^9+7$ 取模.

$1\le l\le r\le 3\times 10^{4}1\; \backslash leq\; l\; \backslash leq\; r\; \backslash leq\; 3\; \backslash times\; 10^4$.

分析

经典题了属于是.

对 $[l,r][l,r]$ 所有的合数做质因数分解，记录每个质因子的最大次幂，就完了.

代码

#include <bits/stdc++.h>
using namespace std;

template <typename T>
inline void scan(T& x) {
	x = 0; int f = 1; char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
	while(isdigit(ch))  {x = x * 10 + ch - '0', ch = getchar();}
	x *= f;
}

template <typename T>
void print(T x) {
	if(x < 0) putchar('-'), x = -x;
	if(x > 9) print(x / 10);
	putchar(x % 10 + '0');
}

template <typename T>
void print(T x, char ch) {
	print(x), putchar(ch);
}

typedef double db;
typedef long long ll;
typedef unsigned long long ull;

const db eps = 1e-6;
const int M = (int)1e5;
const int N = (int)1e5;
const ll mod = (ll)1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll linf = 0x3f3f3f3f3f3f3f3f;

bool is_prime[M + 5];
int prime[M + 5], cnt;
int v[M + 5];

void init()
{
    memset(is_prime, 1, sizeof(is_prime));
    is_prime[0] = is_prime[1] = 0;
    for(int i = 2; i <= M; ++i)
    {
        if(is_prime[i])
        {
            prime[++cnt] = i;
            v[i] = i;
        }
        for(int j = 1; j <= cnt && i * prime[j] <= M; ++j)
        {
            is_prime[i * prime[j]] = 0;
            v[i * prime[j]] = prime[j];
            if(i % prime[j] == 0)
            {
                break;
            }
        }
    }
}

ll quick(ll a, ll b, ll p = mod)
{
    ll s = 1;
    while(b)
    {
        if(b & 1) s = s * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return s % p;
}

map<int, int> mp;

void work() {
    int l, r; scan(l), scan(r);
    for(int i = l; i <= r; ++i) if(!is_prime[i]) {
        int j = i;
        while(j > 1) {
            int x = v[j], c = 0;
            while(j % x == 0) j /= x, ++c;
            mp[x] = max(mp[x], c);
        }
    }
    if(mp.empty()) return print(-1, '\n'), void();
    int ans = 1;
    for(auto x: mp) ans = (ll)ans * quick(x.first, x.second) % mod;
    print(ans, '\n');
}

int main() {
	/*ios::sync_with_stdio(0);
	  cin.tie(0); cout.tie(0);*/
//	freopen("in", "r", stdin);
//	freopen("out", "w", stdout);
    init();
	int T = 1; //scan(T);
	for(int ca = 1; ca <= T; ++ca) {
		work();
	}
//	cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
	return 0;
}

Problem K. 小红的真真假假签到题题

题目大意

给一个正整数 $xx$，要求构造正整数 $yy$，满足：

1. $yy$ 是 $xx$ 的倍数，且 $xx$ 和 $yy$ 不能相等.
2. $xx$ 在二进制表示下（为一个01串）是 $yy$ 的二进制表示的一个子串。且 $xx$ 和 $yy$ 的二进制表示的1的个数不能相同.
3. $yy$ 必须为不超过 $10^{19}10^\{19\}$ 的正整数.

$1\le x\le 10^{9}1\; \backslash leq\; x\; \backslash leq\; 10^9$.

分析

性质种出现二进制，肯定从二进制上考虑，显然 就可以.

代码

x=int(input())
print((x<<30)+x)

Problem L. 在这冷漠的世界里光光哭哭

题目大意

给一个长度为 $nn$ 的字符串 $ss$ 和 $qq$ 次询问.

每次询问给出 $ll$, $rr$ 和一个长度为 $33$ 的字符串 $tt$，问字符串 $s[l,r]s[l,r]$ 中存在多少个子序列是 $tt$.

$1\le n\le 8\times 10^4,1\le q\le 5\times 10^5,s[i],t[i]\in {\{}^{\mathrm{\prime }}{a}^{\mathrm{\prime }}{-}^{\mathrm{\prime }}{z}^{\mathrm{\prime }}\}1\; \backslash leq\; n\; \backslash leq\; 8\; \backslash times\; 10^4,\; 1\; \backslash leq\; q\; \backslash leq\; 5\; \backslash times\; 10^5,\; s[i],t[i]\; \backslash in\; \backslash \{\text{'}a\text{'}-\text{'}z\text{'}\backslash \}$.

分析

呜呜，这题想了好久，太久没训练，感觉脑袋傻掉了.

直接分块就行了，预处理一些信息，然后按照 $tt$ 的三个字符在块的位置分讨论.

不过这貌似不是正解（乱搞

代码

#include <bits/stdc++.h>
using namespace std;

template <typename T>
inline void scan(T& x) {
	x = 0; int f = 1; char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
	while(isdigit(ch))  {x = x * 10 + ch - '0', ch = getchar();}
	x *= f;
}

template <typename T>
void print(T x) {
	if(x < 0) putchar('-'), x = -x;
	if(x > 9) print(x / 10);
	putchar(x % 10 + '0');
}

template <typename T>
void print(T x, char ch) {
	print(x), putchar(ch);
}

typedef double db;
typedef long long ll;
typedef unsigned long long ull;

const db eps = 1e-6;
const int M = (int)8e4;
const int N = (int)3e2;
const ll mod = (ll)1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll linf = 0x3f3f3f3f3f3f3f3f;

int n, m, block;
char s[M + 5];
int id[M + 5];
int f[N + 5][26][26][26];
int sum[N + 5][26][26][26];
int g[N + 5][26][26];
int h[N + 5][26];
int L[N + 5], R[N + 5];

void parse() {
    for(int i = 1; i <= n; ++i) id[i] = (i - 1) / block + 1;
    for(int l = 1, r = 0; l <= n; l = r + 1) {
        while(r + 1 <= n && id[l] == id[r + 1]) ++r;
        L[id[l]] = l, R[id[l]] = r;
        for(int i = l; i <= r; ++i) {
            for(int j = 0; j < 26; ++j) {
                for(int k = 0; k < 26; ++k) {
                    f[id[l]][j][k][s[i] - 'a'] += g[id[l]][j][k];
                }
                g[id[l]][j][s[i] - 'a'] += h[id[l]][j];
            }
            h[id[l]][s[i] - 'a']++;
        }
    }
    for(int i = 0; i < 26; ++i) {
        for(int j = 0; j < 26; ++j) {
            for(int k = 0; k < 26; ++k) {
                for(int l = 1; l <= id[n]; ++l) sum[l][i][j][k] = sum[l - 1][i][j][k] + f[l][i][j][k];
            }
        }
    }
}

ll bao(int l, int r, char t[]) {
    int pre = (s[l] == t[1]), suf = 0;
    for(int i = l + 2; i <= r; ++i) if(s[i] == t[3]) ++suf;
    ll ans = 0;
    for(int i = l + 1; i + 1 <= r; ++i) {
        if(s[i] == t[2]) ans += (ll)pre * suf;
        if(s[i] == t[1]) ++pre;
        if(s[i + 1] == t[3]) --suf;
    }
    return ans;
}

ll cal_abc(int l, int r, char t[]) {
    ll ans = bao(l, R[id[l]], t) + bao(L[id[r]], r, t);
    ans += sum[id[r] - 1][t[1] - 'a'][t[2] - 'a'][t[3] - 'a'] - sum[id[l]][t[1] - 'a'][t[2] - 'a'][t[3] - 'a'];
    return ans;
}

ll cal_ab_c(int l, int r, char t[]) {
    int pre = 0, suf = 0, cnt = 0;
    ll ans = 0;
    for(int i = L[id[r]]; i <= r; ++i) if(s[i] == t[3]) ++suf;
    for(int i = id[l] + 1; i < id[r]; ++i) suf += h[i][t[3] - 'a'];
    for(int i = l; i <= R[id[l]]; ++i) {
        if(s[i] == t[2]) cnt += pre;
        if(s[i] == t[1]) pre++;
    }
    ans += (ll)cnt * suf;
    for(int i = id[l] + 1; i < id[r]; ++i) {
        suf -= h[i][t[3] - 'a'];
        ans += (ll)g[i][t[1] - 'a'][t[2] - 'a'] * suf;
    }
//    printf("ab_c: %lld\n", ans);
    return ans;
}

ll cal_a_bc(int l, int r, char t[]) {
    int pre = 0, suf = 0, cnt = 0;
    ll ans = 0;
    for(int i = L[id[r]]; i <= r; ++i) {
        if(s[i] == t[3]) cnt += pre;
        if(s[i] == t[2]) pre++;
    }
    pre = 0;
    for(int i = l; i <= R[id[l]]; ++i) if(s[i] == t[1]) ++pre;
    for(int i = id[l] + 1; i < id[r]; ++i) pre += h[i][t[1] - 'a'];
    ans += (ll)pre * cnt;
    for(int i = id[r] - 1; i > id[l]; --i) {
        pre -= h[i][t[1] - 'a'];
        ans += (ll)pre * g[i][t[2] - 'a'][t[3] - 'a'];
    }
//    printf("a_bc: %lld\n", ans);
    return ans;
}

ll cal_a_b_c(int l, int r, char t[]) {
    int pre = 0, suf = 0;
    ll ans = 0;
    for(int i = l; i <= R[id[l]]; ++i) if(s[i] == t[1]) ++pre;
    for(int i = L[id[r]]; i <= r; ++i) if(s[i] == t[3]) ++suf;
    for(int i = id[l] + 2; i < id[r]; ++i) suf += h[i][t[3] - 'a'];
    for(int i = id[l] + 1; i < id[r]; ++i) {
        ans += (ll)pre * h[i][t[2] - 'a'] * suf;
        pre += h[i][t[1] - 'a'];
        suf -= h[i + 1][t[3] - 'a'];
    }
//    printf("a_b_c: %lld\n", ans);
    return ans;
}

ll cal(int l, int r, char t[]) {
    return cal_abc(l, r, t)
         + cal_ab_c(l, r, t)
         + cal_a_bc(l, r, t)
         + cal_a_b_c(l, r, t);
}

void work() {
    scan(n), scan(m); block = (int)sqrt(n);
    scanf("%s", s + 1);
    parse();
    char t[5]; int l, r;
    for(int _ = 1; _ <= m; ++_) {
        scan(l), scan(r), scanf("%s", t + 1);
        if(id[r] - id[l] + 1 <= 2) {
            print(bao(l, r, t), '\n');
        } else {
            print(cal(l, r, t), '\n');
        }
    }
}

int main() {
	/*ios::sync_with_stdio(0);
	  cin.tie(0); cout.tie(0);*/
//	freopen("big.out", "r", stdin);
//	freopen("out", "w", stdout);
	int T = 1; //scan(T);
	for(int ca = 1; ca <= T; ++ca) {
		work();
	}
//	cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
	return 0;
}