首页 > 代码库 > bzoj 4810 由乃的玉米田 - bitset - 莫队算法
bzoj 4810 由乃的玉米田 - bitset - 莫队算法
由乃在自己的农田边散步，她突然发现田里的一排玉米非常的不美。这排玉米一共有N株，它们的高度参差不齐。
由乃认为玉米田不美，所以她决定出个数据结构题
这个题是这样的：
给你一个序列a，长度为n，有m次操作，每次询问一个区间是否可以选出两个数它们的差为x，或者询问一个区间是
否可以选出两个数它们的和为x，或者询问一个区间是否可以选出两个数它们的乘积为x ，这三个操作分别为操作1
,2,3选出的这两个数可以是同一个位置的数
Input
第一行两个数n,m
后面一行n个数表示ai
后面m行每行四个数opt l r x
opt表示这个是第几种操作，l,r表示操作的区间，x表示这次操作的x
定义c为每次的x和ai中的最大值，ai >= 0，每次的x>=2n,m,c <= 100000
Output
对于每个询问，如果可以，输出yuno，否则输出yumi
Sample Input
5 51 1 2 3 42 1 1 21 1 2 23 1 1 13 5 5 161 2 3 4
Sample Output
yunoyumiyunoyunoyumi
题目大意 (数据结构裸题不需要大意)。（这是由乃OI？）
显然bitset(别问我怎么知道的)。
然而考虑分块，MLE？所以果断否决掉。
是有个基于分块有很省内存的算法？莫队啊，我们只需要2个bitset和一个cnt数组就好了。
现在来考虑具体的操作。
1)区间内是否存在两个数差为x。这个很简单，bitset一个基本的应用。bitset维护一个值域，然后将所有数都减去x(相当于将这个bitset右移x位)，再看有没有数相等(新bitset按位与旧bitset得到的bitset是否存在某一位为1，调用它的函数any()就好了)
2)区间内是否存在两个数和为x。考虑a + b = x,加法不是很好处理，就转化成减法，得到a - (-b) = x。因为bitset不支持负数下标，把大小增大常数又变大，所以考虑用2个bitset。新的bitset维护某一个上限加上-b后的值域。查询的时候我们希望将第一个bitset右移x位，显然负数位才有价值，但是右移溢出的比特位会被直接舍去。所以考虑向左移，把右移x后，没有溢出的部分全部删去。这样的话就左移(limit - x)位，在和第二个bitset进行按位与，然后判断是否存在某一位为1。
3)还是bitset？想多了。。。Tag害死人啊。。值域只有1e5。是不是直接根号大暴力(枚举因子)就完事了？(然后我忘判因子了，就WA了几次)
Code
1 /** 2 * bzoj 3 * Problem#4810 4 * Accepted 5 * Time:13672ms 6 * Memory:4472 7 */ 8 #include<bits/stdc++.h> 9 using namespace std;10 typedef bool boolean;11 12 typedef class Query {13 public:14 int opt;15 int l;16 int r;17 int x;18 int lid;19 int id;20 21 Query():opt(opt), l(l), r(r), x(x), lid(lid) { }22 23 boolean operator < (Query b) const {24 if(lid != b.lid) return lid < b.lid;25 return r < b.r; 26 } 27 }Query;28 29 #define limit 10000130 int n, m, cs;31 int *arr;32 bitset<100005> s, s1, rs;33 Query* qs;34 inline void init() {35 scanf("%d%d", &n, &m);36 arr = new int[(n + 1)];37 qs = new Query[(m + 1)];38 cs = sqrt(n + 0.5);39 for(int i = 1; i <= n; i++)40 scanf("%d", arr + i);41 for(int i = 1; i <= m; i++) {42 scanf("%d%d%d%d", &qs[i].opt, &qs[i].l, &qs[i].r, &qs[i].x);43 qs[i].lid = qs[i].l / cs, qs[i].id = i;44 }45 }46 47 boolean *res;48 int cnt[100005];49 inline void extends(int pos, int val) {50 cnt[arr[pos]] += val; 51 if(cnt[arr[pos]] == 1) s[arr[pos]] = 1, rs[limit - arr[pos]] = 1;52 if(cnt[arr[pos]] == 0) s[arr[pos]] = 0, rs[limit - arr[pos]] = 0;53 }54 55 inline void solve() {56 res = new boolean[(m + 1)];57 sort(qs + 1, qs + m + 1);58 int mdzzl = 1, mdzzr = 0;59 boolean aFlag = false;60 for(int i = 1; i <= m; i++) {61 while(mdzzr < qs[i].r) extends(++mdzzr, 1);62 while(mdzzr > qs[i].r) extends(mdzzr--, -1);63 while(mdzzl > qs[i].l) extends(--mdzzl, 1);64 while(mdzzl < qs[i].l) extends(mdzzl++, -1);65 switch(qs[i].opt) {66 case 1:67 s1 = (s << qs[i].x) & s;68 res[qs[i].id] = s1.any();69 break;70 case 2:71 s1 = (s << (limit - qs[i].x)) & rs;72 res[qs[i].id] = s1.any();73 break;74 case 3:75 aFlag = false;76 for(int j = 1; j * j <= qs[i].x; j++)77 if((qs[i].x % j == 0) && s[j] && s[qs[i].x / j]) {78 aFlag = true;79 break;80 }81 res[qs[i].id] = aFlag;82 break;83 default:84 break;85 }86 }87 for(int i = 1; i <= m; i++)88 puts((res[i]) ? ("yuno") : ("yumi"));89 }90 91 int main() {92 init();93 solve();94 return 0;95 }
bzoj 4810 由乃的玉米田 - bitset - 莫队算法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。