端点区间影响

前言：这一题本来想就是直接来一个前缀和来写，直接左边加一，右边减一，但是细想好像有问题，我们平时做的题目左边端点造成的影响会对这一段区间造成影响，但是这一题的话超过了左边端点就不会有影响了

在这里插入图片描述

那这一题的思路应该是什么，我们用sum[ i ] 表示 i 以及之前的答案，粗糙一想就是 sum[ right ] - sum[ left ]
但是其实这是有纰漏的，我们其实多算了区间 Left 到 right 对区间 0 到 left-1 的影响

又犯了要给sb的错误, (a-b) 要取模的话 ( ( a-b ) % Mod + Mod ) % Mod

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;#define ll long long 
const int Mod = 998244353;
int n, m;
const int N = (int)2e5 + 5;
int a[N];string s;
ll sum0[N], sum1[N], num0[N], num1[N];
ll ans[N];
signed main() {cin >> n >> m;cin >> s;for (int i = 0; i < s.size(); i++) {int u = s[i] - '0';int pos = i + 1;ans[pos] += ans[pos - 1];ll t = 0;num0[pos] = num0[pos - 1] + (u == 0);num1[pos] = num1[pos - 1] + (u == 1);sum0[pos] = sum0[pos - 1];sum1[pos] = sum1[pos - 1];if (u) {t = (num0[pos - 1] * pos - sum0[pos - 1]) % Mod;sum1[pos] = (pos + sum1[pos]) % Mod;}else {t = (num1[pos - 1] * pos - sum1[pos - 1]) % Mod;sum0[pos] = (sum0[pos] + pos) % Mod;}ans[pos] += t;sum0[pos] %= Mod; sum1[pos] %= Mod;ans[pos] = (ans[pos] % Mod + Mod) % Mod;}while (m--) {int l, r;cin >> l >> r;ll t = (ans[r] - ans[l - 1]) % Mod;ll one = (num0[l - 1] * (sum1[r] - sum1[l - 1]) % Mod - (num1[r] - num1[l - 1]) * (sum0[l - 1]) % Mod) % Mod;ll zero = (num1[l - 1] * (sum0[r] - sum0[l - 1]) % Mod - (num0[r] - num0[l - 1]) * (sum1[l - 1]) % Mod) % Mod;cout << ((t - one - zero ) % Mod + Mod) % Mod << endl;}return 0;
}