# 12602 - OuQ String

> author: tangerine1202, ryona, atsushi
###### tags: `csst`

---

## Brief
有以下三種解法

:::info
## Keyword List
英文 | 中文 | 補充或連結
--------|--------|--------
:::

## Solution 1
### 變數、函式定義
- `ll len[k]`：S~k~的字串長度。
- `void solve(ll l, ll r, int k)`
- `ls`、`rs`：將查詢區間從對齊S~k~開頭，改為對齊關注部分開頭，方便比對。（s意指shift）
- 功能：輸出S~k~[l~r]字串

### 想法：
- 先觀察S~k~ = "O" + S~k-1~ + "u" + S~k-1~ + "Q"，k<=50。
S~50~的長度約等於2^50^(≒10^15^)，而char陣列至多開到10^9^左右，故無法以陣列模擬。
- 考慮以遞迴處理。將S~k~拆成"O"、S~k-1~、"u"、S~k-1~、"Q"，五個部分。

### `void solve(ll l, ll r, int k)`
- Basic step
- 當k==1時，直接輸出"OuQ"中被查詢的部分。
- Recursion step
- S~k-1~部分：如果查詢區間涵蓋S~k-1~，則維護左右界後遞迴S~k-1~。
- "O"、"u"、"Q"部分：如在查詢區間內，則直接輸出。

#include <stdio.h>
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
typedef long long ll;
const ll inf = 1e18;
ll len[60];

void solve(ll l, ll r, ll k)
{
    if (k == 1) {
        for (int i = l; i <= r; i++)
            printf("%c", "OuQ"[i]);
        return;
    }
    
    // O
    ll ls = l, rs = r;
    if (ls <= 0 && 0 <= rs)
        printf("O");

    // S_k-1
    ls = l - 1;
    rs = r - 1;
    if (0 <= rs && ls <= len[k - 1] - 1)
        solve(
            max(ls, 0),
            min(rs, len[k - 1] - 1),
            k - 1);

    // u
    ls = l - 1 - len[k - 1];
    rs = r - 1 - len[k - 1];
    if (ls <= 0 && 0 <= rs)
        printf("u");

    // S_k-1
    ls = l - 1 - len[k - 1] - 1;
    rs = r - 1 - len[k - 1] - 1;
    if (0 <= rs && ls <= len[k - 1] - 1)
        solve(
            max(ls, 0),
            min(rs, len[k - 1] - 1),
            k - 1);

    // Q
    ls = l - 1 - len[k - 1] - 1 - len[k - 1];
    rs = r - 1 - len[k - 1] - 1 - len[k - 1];
    if (ls <= 0 && 0 <= rs)
        printf("Q");
}

int main()
{
    int n = 1;
    len[1] = 3;
    // while( 2*len[n]+3 <= inf )
    // 但因 2*len[n]+3 可能會溢位，故移項以防止溢位問題
    while ((inf - 3) / 2 > len[n]) {
        n++;
        len[n] = len[n - 1] * 2 + 3;
    }

    ll l, r, k;
    while (scanf("%lld%lld%lld", &k, &l, &r) != EOF) {
        solve(l, r, k);
        printf("\n");
    }

    return 0;
}
// By tangerine1202

## Solution 2
概念與解法一差不多，但可能有比較白話
由以下兩個步驟推廣。

-----處理k很小的時候：
依據題目，可以設計出
'O' + (k-1) + 'u' + (k-1) + 'Q'
的遞迴式，而且不必優化。

-----對於k比較大的想法：
tmp是指k級字串的第tmp個字元 ( 字串是想像的 ) 。
我們需要判斷tmp是否在左界和右界之間。
如果是，就輸出。

先一層一層進入遞迴，若是tmp + 下一層的字串長度
( len[k] )仍然比左界還要小，就直接讓tmp+=len[k]，並且return回到上一層。

#include <stdio.h>

int k;
long long l, r, tmp, len[53], r1;

void rec(int k){
    if( tmp+len[k] <= l ){    //優化時間複雜度
        tmp+=len[k];
        return ;
    }
    else if(tmp <= r){    //如果tmp>r，直接return
        if(tmp >= l && tmp <= r) printf("O"); 
        tmp++;
        if(k!=1 && tmp <= r) rec(k-1);
        if(tmp >= l && tmp <= r) printf("u"); 
        tmp++;
        if(k!=1 && tmp <= r) rec(k-1);
        if(tmp >= l && tmp <= r) printf("Q"); 
        tmp++;
    }//tmp在範圍內就print，k不等於1以及tmp在範圍內就遞迴
    else return ;
}

//反正長度都固定，用陣列記下來可以省時間(dp)
long long lenk(int k){    
    if(len[k]) return len[k];
    if(k==1) return len[1] = 3;
    return len[k] = 3 + 2*lenk(k-1);
}

int main(){
    lenk(50);
    while( scanf("%d %lld %lld", &k, &l, &r)!=EOF ){
        tmp = 0;
        rec(k);
        printf("\n");
    }
    return 0;
}

// By ryona

## Solution 3

#include <stdio.h>
long long length[53],l , r;;
int k;
char s1[5] = "OuQ";
char askingchar(int linex, long long chdex){ // linex 是等同於k 
                                            // chdex 等同於k行的幾個字(0開始)
    if(linex == 1) // 遞迴到1
        return s1[chdex];
    if(chdex == 0) // 剛好要第一個字，一定是O
        return 'O';
    else if (chdex == length[linex]-1) // 剛好要最後一個字，一定是Q
        return 'Q';
    else if (chdex == length[linex-1]+1) // 剛好要中間字，一定是u
        return 'u';
    else
    {
        if(chdex < length[linex-1]+1)
            return askingchar(linex-1,chdex-1); // 將chdex 換算成上一行的第幾個字
        else 
             return askingchar(linex-1,chdex-length[linex-1]-2); // 同理，換算
    }
}

int main(){
    length[1] = 3;
    for(int i=2;i<=53;i++){
        length[i] = 2 * length[i-1] + 3;
    }
    
    while(~scanf("%d %lld %lld", &k, &l, &r)){
        for(int i=l;i<=r;i++){
            printf("%c",askingchar(k,i));
        }
        printf("\n");
    }
    return 0;
}
// By atsushi

## Solution 4

#include <stdio.h>

long long k, l, r, len;

char search(long long n, long long len, long long k);

int main() {
    while (scanf("%lld %lld %lld", &k, &l, &r) == 3) {
        len = 3 * (1ll << k) - 3; // count the length
        for (long long i = l; i <= r; i++) printf("%c", search(i, len, k));
        printf("\n");
    }
}

char search(long long n, long long len, long long k) {
    if (n < k) return 'O'; // 前k項必為'O'
    if (n == (len-1) / 2) return 'u'; // 中間項必為'u'
    if (n > len-1-k) return 'Q'; // 後k項必為'Q'
    
    // 將字串拆成 O, sk-1, u, sk-1, Q 五個部分
    len = (len-3) / 2;
    if (n > len) return search(n-len-2, len, k-1); // 第2段sk-1
    else return search(n-1, len, k-1); // 第1段sk-1
}

// By Utin

## Reference