【BZOJ 4523】[Cqoi2016] 路由表

Qizy Trie, 字符串, 解题报告

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4523
数据生成器：http://paste.ubuntu.com/23140079/

这个题，Trie树的做法很显然，可以持久，也可以不持久
但此题卡常QAQ
在BZOJ上过的不算，是男人就上Super OJ去交
我被逼着优化成了BZOJ上的Rank11才在SOJ上刚好卡过 (╯‵□′)╯︵┻━┻

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 1000000+9;
const int M = 33000000;

int Stack[N];
bool ip[40];

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
	return ret*f;
}

namespace Trie{
	#define TRE Trie
	int tot=1,ch[M][2],cnt,root=1,end[M];
	
	inline void modify(int len){
		int w = root; 
		for (int i=1;i<=len;i++) {
			int c = ip[i];
			if (ch[w]) w = ch[w];
			else w = ch[w] = ++tot;
		}
		end[w] = ++cnt;
	}
	
	inline int query(int l, int r){
		int top = 0, w = root, t = 1;
		while (w) {
			if (end[w]) {
				while (top && Stack[top] > end[w]) top--;
				Stack[++top] = end[w];
			}	
			w = ch[w][ip[t]]; t++;
		} t = 0;
		for (int i=1;i<=top;i++) 
			if (Stack[i] > r) break;
			else if (Stack[i] >= l) t++;
		return t;
	}
};

inline void Get_IP(){
	memset(ip,0,sizeof(ip));
	for (int j=1,sta=9;j<=4;j++,sta+=8) {
		int TP = read(), i = 1;
		while (TP) ip[sta-i] = TP & 1, TP >>= 1, i++; 
	}
}

int main(){
	for (int k=read(),a,b;k;k--) {
		char c=getchar(); 
		while (c != 'A' && c != 'Q') c=getchar();
		if (c == 'A') {
			Get_IP();
			TRE::modify(read());
		} else {
			Get_IP();
			a = read(); b = read();
			printf("%d\n",TRE::query(a,b));
		}
	}
	return 0;
}

252 thoughts to “【BZOJ 4523】[Cqoi2016] 路由表”

  91. As I web site possessor I believe the content matter here is rattling magnificent , appreciate it for your hard work. You should keep it up forever! Best of luck.

    Reply

  194. I just like the helpful info you supply for your articles. I’ll bookmark your blog and take a look at again right here frequently. I am relatively certain I will be told lots of new stuff proper right here! Good luck for the next!

    Reply

  212. Magnificent beat ! I wish to apprentice while you amend your site, how can i subscribe for a blog site? The account aided me a acceptable deal. I had been tiny bit acquainted of this your broadcast provided bright clear idea|

    Reply

  219. I am really enjoying the theme/design of your web site. Do you ever run into any internet browser compatibility problems? A handful of my blog visitors have complained about my site not operating correctly in Explorer but looks great in Firefox. Do you have any tips to help fix this issue?|

    Reply

  224. Great post. I was checking continuously this blog and I am impressed! Very helpful info particularly the last part 🙂 I care for such information much. I was looking for this certain info for a long time. Thank you and good luck.|

    Reply

  230. Thanks for some other magnificent article. Where else could anyone get that kind of info in such an ideal means of writing? I have a presentation next week, and I’m on the search for such info.|

    Reply

  233. Hi I am so grateful I found your website, I really found you by error, while I was searching on Bing for something else, Nonetheless I am here now and would just like to say thank you for a remarkable post and a all round interesting blog (I also love the theme/design), I don’t have time to browse it all at the minute but I have book-marked it and also added your RSS feeds, so when I have time I will be back to read a great deal more, Please do keep up the excellent b.|

    Reply

  238. I’m not sure where you’re getting your info, but good topic. I needs to spend some time learning much more or understanding more. Thanks for fantastic information I was looking for this information for my mission.|

    Reply

  239. Hey! I know this is kind of off topic but I was wondering which blog platform are you using for this site? I’m getting sick and tired of WordPress because I’ve had issues with hackers and I’m looking at alternatives for another platform. I would be awesome if you could point me in the direction of a good platform.|

    Reply

  246. Yesterday, while I was at work, my cousin stole my iPad and tested to see if it can survive a thirty foot drop, just so she can be a youtube sensation. My iPad is now broken and she has 83 views. I know this is totally off topic but I had to share it with someone!|

    Reply

  251. Woah! I’m really enjoying the template/theme of this blog. It’s simple, yet effective. A lot of times it’s very hard to get that “perfect balance” between superb usability and visual appeal. I must say that you’ve done a excellent job with this. Additionally, the blog loads extremely fast for me on Chrome. Outstanding Blog!|

    Reply

  252. I’m excited to uncover this website. I want to to thank you for your time for this particularly fantastic read!! I definitely really liked every part of it and i also have you book-marked to check out new stuff on your site.|

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *