E. Lucky Queries
Petya loves lucky numbers very much. Everybody knows that lucky numbers are positive integers whose decimal record contains only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.
Petya brought home string s with the length of n. The string only consists of lucky digits. The digits are numbered from the left to the right starting with 1. Now Petya should execute m queries of the following form:
Subsequence of a string s is a string that can be obtained from s by removing zero or more of its elements. A string is called non-decreasing if each successive digit is not less than the previous one.
Help Petya process the requests.
InputThe first line contains two integers n and m (1?≤?n?≤?106,?1?≤?m?≤?3·105) — the length of the string s and the number of queries correspondingly. The second line contains n lucky digits without spaces — Petya's initial string. Next m lines contain queries in the form described in the statement.
OutputFor each query count print an answer on a single line.
Sample test(s) input2 3 47 count switch 1 2 countoutput
2 1數據量好大,使用線段樹查詢可以大大提高速度。
本題關鍵難點是線段樹的動態更新,需要設置一個Lazy標志,就是不需要每次更新所有點,而是等到下次需要查詢到這個點的時候,更新這個點的兩個孩子節點。
其中的邏輯關系,需要好好研究研究代碼吧。 沒搞清其中的邏輯,還是十分有難度的。
線段樹本題就兩個點了:
1 二分法操作樹
2 Lazy標志動態更新區間
#include#include #include #include #include using namespace std; class LuckyQueries { int n, tSize; char *str; struct Node { int L4, L7, L47, L74; bool lazy; }; Node *segTree; void updateNode(int id, int left, int right) { segTree[id].L4 = segTree[left].L4 + segTree[right].L4; segTree[id].L7 = segTree[left].L7 + segTree[right].L7; int a = segTree[left].L47 + segTree[right].L7; int b = segTree[left].L4 + segTree[right].L47; segTree[id].L47 = max(a, b); a = segTree[left].L74 + segTree[right].L4; b = segTree[left].L7 + segTree[right].L74; segTree[id].L74 = max(a, b); segTree[id].lazy = false; } void conHelper(int low, int up, int id = 0) { if (low == up) { if (str[low] == '4') { segTree[id].L4 = 1, segTree[id].L7 = 0; segTree[id].L47 = 1, segTree[id].L74 = 0; } else { segTree[id].L4 = 0, segTree[id].L7 = 1; segTree[id].L47 = 0, segTree[id].L74 = 1; } segTree[id].lazy = false; return ; } int mid = low + ((up-low)>>1); int left = id*2+1; int right = id*2+2; conHelper(low, mid, left); conHelper(mid+1, up, right); updateNode(id, left, right); } void conTree() { int h = (int) ceil((double)log(double(n))/log(2.0)) + 1; tSize = (int) pow(2.0, double(h)) - 1; segTree = (Node *) malloc(sizeof(Node) * tSize); conHelper(0, n-1); } inline int getLongestIncease() { return max(segTree[0].L4, max(segTree[0].L47, segTree[0].L7)); } void invert(int root) { segTree[root].lazy = !segTree[root].lazy; swap(segTree[root].L4, segTree[root].L7); swap(segTree[root].L47, segTree[root].L74); } void updateTree(const int low, const int up, int tLow, int tUp, int root = 0) { if (tUp < low || up < tLow)//錯寫||成&& { return ; } if (low <= tLow && tUp <= up) { invert(root); return ; } int tMid = tLow + ((tUp-tLow)>>1); int left = root * 2 + 1; int right = root * 2 + 2; if (segTree[root].lazy) { segTree[root].lazy = false; invert(left); invert(right); } updateTree(low, up, tLow, tMid, left); updateTree(low, up, tMid+1, tUp, right); updateNode(root, left, right); } public: LuckyQueries() { int m; scanf("%d %d", &n, &m); getchar();//別忘記了去掉一個換行符 str = (char *) malloc(sizeof(char) * (n+1)); gets(str); conTree(); char command[8]; for (int i = 0; i < m; i++) { char c = getchar(); if ('c' == c) { printf("%d\n", getLongestIncease()); gets(command);//gets一行 } else { while (c != ' ') c = getchar(); int low, up; scanf("%d %d", &low, &up); updateTree(low-1, up-1, 0, n-1); if (i+1 != m) getchar(); } } } ~LuckyQueries() { if (str) free(str); if (segTree) free(segTree); } };