C. Banh-mi

처음 음식의 맛 0,1이 n개 주어지고 쿼리가 q개 주어진다.

쿼리는 i,j로 구성되어 있으며 [i:j] (i,j를 포함하는 구간)을 최대의 맛을 얻을 수 있도록 먹었을 때의 값을 출력해야 한다.

음식의 순서는 범위 내에서 임의로 정할 수 있으며 음식을 먹으면 먹은 맛만큼의 값이 구간의 음식에 전부 더해진다

1 1 0 1 을 왼쪽에서부터 순서대로 먹는다고 하면

_ 2 1 2 -> _ _ 3 4 -> _ _ _ 7 -> _ _ _ _ = 13 의 결과가 나온다.

잘 보면 처음 먹은 1은 8 = 2^3 번 더해지고 두번째로 먹은 1은 4 = 2^2 번 더해진다.

마지막으로 먹은 1은 한번만 더해지므로 1은 무조건 먼저 먹는게 이득이라는 것을 알 수 있다.

식을 알기위해 11100을 계산해보자

2^4 + 2^3 + 2^2 가 나온다.

2^(구간길이-1) 부터 1의 갯수번 더한다.

따라서 식은 (2^l - 1) - (2^cnt(0) - 1) = 2^l - 2^cnt(0) 이 된다.

쿼리가 10만개이므로 빠르게 처리하기 위해서 2^100000까지 배열에 미리 다 저장하고 1의 개수를 구간합을 통해 O(1)만에 구한다.

#include <iostream>
using namespace std;
 
typedef long long ll;
 
ll n, q, c[100111], d[100111];
const ll mod = 1000000007;
char a[100111];
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n >> q >> a + 1;
    d[0] = 1;
    for (int i = 1; i <= n; ++i) 
        d[i] = (d[i - 1] * 2) % mod;
    for (ll i = 1; i <= n; ++i) 
        c[i] = c[i - 1] + (a[i] == '1');
    while (q--) {
        ll u, v;
        cin >> u >> v;
        ll zeros = v - u + 1 - (c[v] - c[u - 1]);
        cout << (d[v - u + 1] - d[zeros] + mod) % mod << '\n';
    }
    return 0;
}