P4867Gty的二逼妹子序列(莫队+分块)

题目
输入样例#1&＃xff1a;
10 10
4 4 5 1 4 1 5 1 2 1
5 9 1 2
3 4 7 9
4 4 2 5
2 3 4 7
5 10 4 4
3 9 1 1
1 4 5 9
8 9 3 3
2 2 1 6
8 9 1 4

输出样例#1&＃xff1a;
2
0
0
2
1
1
1
0
1
2

【样例的部分解释】
5 9 1 2 子序列为4 1 5 1 2 在[1,2]里的权值有1,1,2&＃xff0c;有2种&＃xff0c;因此答案为2。
3 4 7 9 子序列为5 1 在[7,9]里的权值有5&＃xff0c;有1种&＃xff0c;因此答案为1。
4 4 2 5 子序列为1 没有权值在[2,5]中的&＃xff0c;因此答案为0。
2 3 4 7 子序列为4 5 权值在[4,7]中的有4,5&＃xff0c;因此答案为2。
建议使用输入/输出优化。

思路&＃xff1a;这个题很显然可以用莫队&＃43;树状数组&＃43;vis[]标记解决。

add:x&＃61;a[x];vis[x]&＃43;&＃43;;if(vis[x]&＃61;&＃61;1) modify(x,1).
del:x&＃61;a[x];vis[x]--;if(!vis[x]) modify(x,-1).
query(l,r):if(l!&＃61;1) return getsum(r)-getsum(l-1); else return getsum(r);


modify的复杂度log(n)。每次dexl,dexr移动次数很多。但是query次数是m。
由于这个特性.我们可以采用分块。 还有block1&＃61;block2&＃61;sqrt(n) 。否则TLE。好玄好烦
而且我们这个统计可以全部移动完统计,不是很像以前那种&＃xff0c;dexl,dexr移动期间就必须要求出对res的影响(否则移动完遍历复杂度会白白增大,不如边移动边更新res) (我也说不清)。
add,del&＃xff1a;x&＃61;a[x];tag[x],sum[bl[x]]相应修改
query&＃xff1a;零散&＃43;整块

//一开始是这样写的...一直WA(我脑子进水 我有病!!!)
void change(int x,int val)
{tag[x]&＃43;&＃61;val;if(tag[x]&＃61;&＃61;1)//这个等于1不是啊 我mmp???(改成val&＃61;&＃61;1&&tag[x]&＃61;&＃61;1)就AC.sum[bl[x]]&＃43;&＃43;;if(!tag[x])//这个等于0时肯定是因为val&＃61;-1sum[bl[x]]--;
}
void add(int x){change(a[x],1);
}
void del(int x){change(a[x],-1);
}


#include
#include
#include
#include
#include
#define en &＃39;\n&＃39;
#define foru(i,a,b) for(int i&＃61;a;i<&＃61;b;&＃43;&＃43;i)
#define m(a,b) memset(a,b,sizeof a)
using namespace std;
typedef long long ll;
const int N&＃61;1e5&＃43;5,M&＃61;1e6&＃43;5,INF&＃61;0x3f3f3f3f;
template<class T>void rd(T &x)
{x&＃61;0;int f&＃61;0;char ch&＃61;getchar();while(ch<&＃39;0&＃39;||ch>&＃39;9&＃39;) {f|&＃61;(ch&＃61;&＃61;&＃39;-&＃39;);ch&＃61;getchar();}while(ch>&＃61;&＃39;0&＃39;&&ch<&＃61;&＃39;9&＃39;){x&＃61;(x<<1)&＃43;(x<<3)&＃43;(ch^48);ch&＃61;getchar();}x&＃61;f?-x:x;return;
}
int a[N];
int dexl,dexr;
int ans[M];
struct Query{int id,l,r,u,v;}q[M];
int sum[320],tag[N],bl[N],block;
bool cmp(Query x,Query y)
{if(bl[x.l]&＃61;&＃61;bl[y.l])return x.r<y.r;return bl[x.l]<bl[y.l];
}
int query(int l,int r)
{int ans&＃61;0;for(int i&＃61;l;i<&＃61;min(bl[l]*block,r);i&＃43;&＃43;)if(tag[i]) &＃43;&＃43;ans;if(bl[l]!&＃61;bl[r])for(int i&＃61;(bl[r]-1)*block&＃43;1;i<&＃61;r;i&＃43;&＃43;)if(tag[i]) &＃43;&＃43;ans;for(int i&＃61;bl[l]&＃43;1;i<&＃61;bl[r]-1;i&＃43;&＃43;)ans&＃43;&＃61;sum[i];return ans;
}
void add(int x)
{x&＃61;a[x];tag[x]&＃43;&＃43;;if(tag[x]&＃61;&＃61;1)sum[bl[x]]&＃43;&＃43;;
}
void del(int x)
{x&＃61;a[x];tag[x]--;if(!tag[x])sum[bl[x]]--;
}
int main()
{//m(tag,0);int n,m;rd(n),rd(m);block&＃61;sqrt(n);foru(i,1,n)rd(a[i]),bl[i]&＃61;(i-1)/block&＃43;1;foru(i,1,m)rd(q[i].l),rd(q[i].r),rd(q[i].u),rd(q[i].v),q[i].id&＃61;i;sort(q&＃43;1,q&＃43;m&＃43;1,cmp);dexl&＃61;1,dexr&＃61;0;foru(i,1,m){while(dexr<q[i].r) add(&＃43;&＃43;dexr);while(dexl>q[i].l) add(--dexl);while(dexr>q[i].r) del(dexr--);while(dexl<q[i].l) del(dexl&＃43;&＃43;);ans[q[i].id]&＃61;query(q[i].u,q[i].v);}foru(i,1,m)printf("%d\n",ans[i]);
}