1 #include <set>  2 #include <map>  3 #include <queue>  4 #include <deque>  5 #include <cmath>  6 #include <vector>  7 #include <string>  8 #include <cstdio>  9 #include <cstdlib> 10 #include <cstring> 11 #include <cassert> 12 #include <iostream> 13 #include <algorithm> 14  15 using namespace std; 16  17 typedef long long LL; 18 typedef pair <int, int> PII; 19  20 const int N = 5e4 + 7; 21 const int INF = 0x3f3f3f3f; 22 const int MOD = 1e9 + 7; 23 const double EPS = 1e-12; 24 const double PI = acos(0) * 2; 25  26 struct Node{ 27     int a, b, lazy; 28     LL sum, best; 29     Node *l, *r; 30 }; 31  32 struct SegmentTree{ 33     Node tree[N << 1], *root; 34     int pos; 35      36     Node *build(int a, int b){ 37         Node *root = &tree[++pos]; 38         root->a = a; 39         root->b = b; 40         root->sum = b - a + 1; 41         root->best = 1; 42         root->lazy = 0; 43         if (a == b) 44             return root; 45         int mid = (a + b) >> 1; 46         root->l = build(a, mid); 47         root->r = build(mid + 1, b); 48         return root; 49     } 50      51     void init(int n){ 52         pos = 0; 53         root = build(1, n); 54     } 55      56     void release(Node *root){ 57         if (root->lazy){ 58             root->l->sum <<= root->lazy; 59             root->l->best <<= root->lazy; 60             root->l->lazy += root->lazy; 61             root->r->sum <<= root->lazy; 62             root->r->best <<= root->lazy; 63             root->r->lazy += root->lazy; 64             root->lazy = 0; 65         } 66     } 67      68     void update(Node *root){ 69         root->sum = root->l->sum + root->r->sum; 70         root->best = max(root->l->best, root->r->best); 71     } 72      73     void insert(Node *root, LL a, LL b){ 74         //printf("Insert [%d, %d] of %I64d %I64d\n", root->a, root->b, a, b); 75         if (root->a == root->b){ 76             root->sum += b - a + 1; 77             root->best = root->sum; 78             return; 79         } 80         if (root->sum == b - a + 1){ 81             root->sum <<= 1; 82             root->best <<= 1; 83             ++root->lazy; 84             return; 85         } 86         release(root); 87         LL left = root->l->sum; 88         if (left >= a) 89             insert(root->l, a, min(left, b)); 90         if (left < b) 91             insert(root->r, max(a - left, 1LL), b - left); 92         update(root); 93     } 94      95     void add(LL l, LL r){ 96         insert(root, l, r); 97     } 98      99     LL find(Node *root, LL a, LL b){100         if (root->a == root->b){101             return b - a + 1;102         }103         if (root->sum == b - a + 1){104             return root->best;105         }106         release(root);107         LL ret = 0;108         if (root->l->sum >= a)109             ret = max(ret, find(root->l, a, min(root->l->sum, b)));110         if (root->l->sum < b)111             ret = max(ret, find(root->r, max(a - root->l->sum, 1LL), b - root->l->sum));112         //update(root);113         return ret;114     }115     116     LL query(LL l, LL r){117         return find(root, l, r);118     }119     120     void debug(){121         for (int i = 1; i <= pos; ++i)122             printf("%d - %d : sum %I64d best %I64d lazy %d\n", tree[i].a, tree[i].b, tree[i].sum, tree[i].best, tree[i].lazy);123     }124 }tree;125 126 int main(){127     //freopen("a.in", "r", stdin);128     //freopen("a.out", "w", stdout);129     int T, n, m;130     char op[10];131     LL x, y;132     scanf("%d", &T);133     for (int Test = 1; Test <= T; ++Test){134         scanf("%d%d", &n, &m);135         tree.init(n);136         //tree.debug();137         printf("Case #%d:\n", Test);138         for (int i = 1; i <= m; ++i){139             scanf(" %s%I64d%I64d", op, &x, &y);140             if (op[0] == ‘D‘)141                 tree.add(x, y);142             else143                 printf("%I64d\n", tree.query(x, y));144             //tree.debug();145         }146     }147     148     return 0;149 }