程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Codeforce E. Lucky Queries 線段樹實踐

Codeforce E. Lucky Queries 線段樹實踐

編輯:C++入門知識

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:

  • switch l r — "switch" digits (i.e. replace them with their opposites) at all positions with indexes from l to r, inclusive: each digit 4 is replaced with 7 and each digit 7 is replaced with 4 (1?≤?l?≤?r?≤?n);
  • count — find and print on the screen the length of the longest non-decreasing subsequence of string s.

    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.

    Input

    The 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.

    Output

    For each query count print an answer on a single line.

    Sample test(s) input
    2 3
    47
    count
    switch 1 2
    count
    
    output
    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);
    	}
    };



  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved