題目大意:D表示在區間x,y內所有的元素擴充一倍;Q表示查詢在這個下表以內的數字最多的個數為多少。
如:1,2,3.D 1 3 之後就變成了 1 1 2 2 3 3.Q 1 4 輸出 2.
解題思路:每個節點記錄兩個信息:最大值的個數以及這個點一共有多少個數字。
1 5 5 D 5 5 Q 5 6 D 2 3 D 1 2 Q 1 7
Case #1: 2 3
#include#include #include #include #include #define LL long long using namespace std; const int maxn = 101000; LL num[maxn<<2]; LL Max[maxn<<2]; void Bulid(int l, int r, int site) { Max[site] = 1LL; if(l == r) { num[site] = 1LL; return; } int mid = (l+r)>>1; Bulid(l, mid, site<<1); Bulid(mid+1, r, site<<1|1); num[site] = num[site<<1]+num[site<<1|1]; } void Push_Up(int site) { Max[site] = max(Max[site<<1], Max[site<<1|1]); num[site] = num[site<<1]+num[site<<1|1]; } void Update(int l, int r, LL ll, LL rr, int site) { if(l == r) { num[site] += (rr-ll+1); Max[site] = num[site]; return; } LL tmp = num[site<<1]; int mid = (l+r)>>1; if(rr <= tmp) Update(l, mid, ll, rr, site<<1); else if(ll > tmp) Update(mid+1, r, ll-tmp, rr-tmp, site<<1|1); else { Update(l, mid, ll, tmp, site<<1); Update(mid+1, r, 1, rr-tmp, site<<1|1); } Push_Up(site); } LL Query(int l, int r, LL ll, LL rr, int site) { if(num[site] == (rr-ll+1)) return Max[site]; if(l == r) return (rr-ll+1); LL tmp = num[site<<1]; int mid = (l+r)>>1; if(rr <= tmp) return Query(l, mid, ll, rr, site<<1); else if(ll > tmp) return Query(mid+1, r, ll-tmp, rr-tmp, site<<1|1); else return max(Query(l, mid, ll, tmp, site<<1), Query(mid+1, r, 1, rr-tmp, site<<1|1)); } int main() { int T; int Case = 1; cin >>T; char str[110]; while(T--) { printf("Case #%d:\n", Case++); int n, m; scanf("%d %d",&n, &m); Bulid(1, n, 1); LL x, y; while(m--) { scanf("%s",str); scanf("%I64d %I64d",&x, &y); if(str[0] == 'D') Update(1, n, x, y, 1); else printf("%I64d\n",Query(1, n, x, y, 1)); } } }