3236: [Ahoi2013]作业
Time Limit: 100 Sec Memory Limit: 512 MBSubmit: 1423 Solved: 572
[Submit][Status][Discuss]
Description
.jpg)
Input
Output
Sample Input
3 4
1 2 2
1 2 1 3
1 2 1 1
1 3 1 3
2 3 2 3
1 2 2
1 2 1 3
1 2 1 1
1 3 1 3
2 3 2 3
Sample Output
2 2
1 1
3 2
2 1
1 1
3 2
2 1
HINT
N=100000,M=1000000
题解
本来以为要用什么高阶的数据结构……结果一看时限……直接上莫队+树状数组吧。树状数组开两个，第一问直接搞，第二问用一个num数组记录每个数字出现次数辅助，num数组从0变1或从1变0才在第二个树状数组中修改。
pascal毫无悬念的T了……上C艹就过了……
我C艹写的好丑
1 #include<iostream> 2 #include<set> 3 #include<map> 4 #include<cstdio> 5 #include<cstring> 6 #include<cstdlib> 7 #include<algorithm> 8 #include<cmath> 9 using namespace std; 10 const int maxn=100086; 11 int read() 12 { 13 int x=0,f=1;char ch=getchar(); 14 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 15 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 16 return x*f; 17 } 18 struct data{int l,r,a,b,bel,id;} op[10*maxn]; 19 int num[maxn],a[maxn],ans[maxn*10][2],c[2][maxn]; 20 int size,n,m; 21 bool cmp(data x,data y) 22 { 23 if(x.bel!=y.bel)return x.bel<y.bel;else return x.r<y.r; 24 } 25 void add(int x,int ps,int dd) 26 { 27 for(int i=ps;i<=n;i+=i&(-i))c[x][i]+=dd; 28 } 29 int ask(int x,int ps) 30 { 31 int sum=0; 32 for(int i=ps;i;i-=i&(-i))sum+=c[x][i]; 33 return sum; 34 } 35 void ins(int x) 36 { 37 if(!num[x])add(1,x,1); 38 num[x]++;add(0,x,1); 39 } 40 void del(int x) 41 { 42 num[x]--;add(0,x,-1); 43 if(!num[x])add(1,x,-1); 44 } 45 void solve() 46 { 47 int l=1,r=0; 48 for(int i=1;i<=m;i++) 49 { 50 while(r<op[i].r)ins(a[++r]); 51 while(l>op[i].l)ins(a[--l]); 52 while(r>op[i].r)del(a[r--]); 53 while(l<op[i].l)del(a[l++]); 54 ans[op[i].id][0]=ask(0,op[i].b)-ask(0,op[i].a-1); 55 ans[op[i].id][1]=ask(1,op[i].b)-ask(1,op[i].a-1); 56 } 57 } 58 int main() 59 { 60 n=read();m=read(); 61 for(int i=1;i<=n;i++)a[i]=read(); 62 size=sqrt(n); 63 for(int i=1;i<=m;i++) 64 { 65 op[i].l=read();op[i].r=read();op[i].a=read();op[i].b=read(); 66 op[i].id=i;op[i].bel=(op[i].l-1)/size+1; 67 } 68 sort(op+1,op+m+1,cmp); 69 solve(); 70 for(int i=1;i<=m;i++)printf("%d %d ",ans[i][0],ans[i][1]); 71 return 0; 72 }
pascal版本果断T掉了
1 program j01; 2 type xx=record l,r,a,b,bel,id:longint; end; 3 var op:array[0..1000086]of xx; 4 num,a:array[0..100086]of longint; 5 c:array[0..1,0..100086]of longint; 6 ans:array[0..1000086,0..1]of longint; 7 n,m,size,i:longint; 8 9 function cmp(x,y:xx):boolean; 10 begin 11 if x.bel<>y.bel then exit(x.bel<y.bel) 12 else exit(x.r<y.r); 13 end; 14 15 procedure qsort(l,r:longint); 16 var i,j:longint;x,y:xx; 17 begin 18 i:=l;j:=r;x:=op[(i+j) div 2]; 19 repeat 20 while cmp(op[i],x) do inc(i); 21 while cmp(x,op[j]) do dec(j); 22 if i<=j then 23 begin 24 y:=op[i];op[i]:=op[j];op[j]:=y; 25 inc(i);dec(j); 26 end; 27 until i>j; 28 if i<r then qsort(i,r); 29 if l<j then qsort(l,j); 30 end; 31 32 procedure add(x,i,dd:longint); 33 begin 34 while i<=n do 35 begin 36 inc(c[x,i],dd); 37 i:=i+(i and(-i)); 38 end; 39 end; 40 41 function ask(x,i:longint):longint; 42 begin 43 ask:=0; 44 while i>0 do 45 begin 46 inc(ask,c[x,i]); 47 i:=i-(i and(-i)); 48 end; 49 end; 50 51 procedure ins(x:longint); 52 begin 53 if num[x]=0 then add(1,x,1); 54 inc(num[x]);add(0,x,1); 55 end; 56 57 procedure del(x:longint); 58 begin 59 dec(num[x]);add(0,x,-1); 60 if num[x]=0 then add(1,x,-1); 61 end; 62 63 procedure solve; 64 var i,l,r:longint; 65 begin 66 fillchar(num,sizeof(num),0); 67 l:=1;r:=0; 68 for i:=1 to m do 69 begin 70 while r<op[i].r do begin inc(r);ins(a[r]); end; 71 while l>op[i].l do begin dec(l);ins(a[l]); end; 72 while r>op[i].r do begin del(a[r]);dec(r); end; 73 while l<op[i].l do begin del(a[l]);inc(l); end; 74 ans[op[i].id,0]:=ask(0,op[i].b)-ask(0,op[i].a-1); 75 ans[op[i].id,1]:=ask(1,op[i].b)-ask(1,op[i].a-1); 76 end; 77 end; 78 79 begin 80 readln(n,m); 81 for i:=1 to n do read(a[i]); 82 size:=trunc(sqrt(n)); 83 for i:=1 to m do 84 begin 85 readln(op[i].l,op[i].r,op[i].a,op[i].b); 86 op[i].id:=i; 87 op[i].bel:=(op[i].l-1)div size+1; 88 end; 89 qsort(1,m); 90 solve; 91 for i:=1 to m do writeln(ans[i,0],' ',ans[i,1]); 92 end.