http://www.pipioj.online/problem.php?id=1295
1 #define bug(x) cout<<#x<<" is "<<x<<endl 2 #define IO std::ios::sync_with_stdio(0) 3 #include<bits/stdc++.h> 4 using namespace std; 5 #define ll long long 6 const int N=3e5+10; 7 typedef struct LinkNode{ 8 int co; 9 int ex; 10 LinkNode *next; 11 }LinkNode,*LinkList; 12 void attach(int co,int ex,LinkNode *&r){ 13 LinkNode *p=(LinkNode *)malloc(sizeof(LinkNode)); 14 p->co=co; 15 p->ex=ex; 16 p->next=NULL; 17 r->next=p; 18 r=p; 19 } 20 LinkList mutiply(LinkList L1,LinkList L2){ 21 LinkNode *front=(LinkNode *)malloc(sizeof(LinkNode)); 22 LinkNode *rear=front; 23 front->next=NULL; 24 LinkNode *r1=L1->next; 25 LinkNode *r2=L2->next; 26 while(r1){ 27 rear=front; 28 while(r2){ 29 int co=r1->co*r2->co; 30 int ex=r1->ex+r2->ex; 31 while(rear->next&&ex>rear->next->ex){ 32 rear=rear->next; 33 } 34 if(rear->next&&ex==rear->next->ex){ 35 if(co+rear->co==0){ 36 LinkNode *p=rear->next; 37 rear->next=p->next; 38 free(p); 39 } 40 else{ 41 rear->next->co+=co; 42 } 43 } 44 else{ 45 if(co!=0){ 46 LinkNode *p=(LinkNode *)malloc(sizeof(LinkNode)); 47 p->co=co; 48 p->ex=ex; 49 p->next=rear->next; 50 rear->next=p; 51 rear=rear->next; 52 } 53 } 54 r2=r2->next; 55 } 56 r1=r1->next; 57 r2=L2->next; 58 } 59 return front; 60 } 61 struct node{ 62 int x,y; 63 }a[N],b[N]; 64 bool cmp(node p,node q){ 65 return p.y<q.y; 66 } 67 int work(node p[],int n1){ 68 sort(p+1,p+1+n1,cmp); 69 int g1=0,n2=0; 70 for(int i=1;i<=n1;i++){ 71 if(i==n1){ 72 p[++n2].y=p[i].y; 73 p[n2].x=g1+p[i].x; 74 break; 75 } 76 if(p[i+1].y==p[i].y){ 77 g1+=p[i].x; 78 } 79 else{ 80 p[++n2].y=p[i].y; 81 p[n2].x=g1+p[i].x; 82 g1=0; 83 } 84 } 85 return n2; 86 } 87 void print(LinkNode *p){ 88 if(p->next)print(p->next); 89 cout<<p->co<<" "<<p->ex<<" "; 90 } 91 int n,m; 92 int main(){ 93 IO; 94 LinkList L1,L2; 95 L1=(LinkList)malloc(sizeof(LinkNode)); 96 L2=(LinkList)malloc(sizeof(LinkNode)); 97 L1->next=NULL; 98 L2->next=NULL; 99 LinkNode *r1=L1,*r2=L2; 100 cin>>n; 101 for(int i=1;i<=n;i++){ 102 cin>>a[i].x>>a[i].y; 103 } 104 int n1=0,n2=0; 105 n1=work(a,n); 106 for(int i=1;i<=n1;i++){ 107 attach(a[i].x,a[i].y,r1); 108 } 109 cin>>m; 110 for(int i=1;i<=m;i++){ 111 cin>>b[i].x>>b[i].y; 112 } 113 n2=work(b,m); 114 for(int i=1;i<=n2;i++){ 115 attach(b[i].x,b[i].y,r2); 116 } 117 LinkList L3=mutiply(L1,L2); 118 L3=L3->next; 119 if(!L3)cout<<"0 0"; 120 else print(L3); 121 } 122 /* 123 3 124 1 3 2 2 4 3 125 3 126 1 7 2 6 3 5 127 */
更新：
1 #define bug(x) cout<<#x<<" is "<<x<<endl 2 #define IO std::ios::sync_with_stdio(0) 3 #include<bits/stdc++.h> 4 using namespace std; 5 #define ll long long 6 const int N=3e5+10; 7 typedef struct LinkNode{ 8 int co; 9 int ex; 10 LinkNode *next; 11 }LinkNode,*LinkList; 12 void attach(int co,int ex,LinkNode *&r){ 13 LinkNode *p=(LinkNode *)malloc(sizeof(LinkNode)); 14 p->co=co; 15 p->ex=ex; 16 p->next=NULL; 17 r->next=p; 18 r=p; 19 } 20 LinkList mutiply(LinkList L1,LinkList L2){ 21 LinkNode *front=(LinkNode *)malloc(sizeof(LinkNode)); 22 LinkNode *rear=front; 23 front->next=NULL; 24 LinkNode *r1=L1->next; 25 LinkNode *r2=L2->next; 26 while(r1){ 27 while(r2){ 28 int co=r1->co*r2->co; 29 int ex=r1->ex+r2->ex; 30 attach(co,ex,rear); 31 r2=r2->next; 32 } 33 r1=r1->next; 34 r2=L2->next; 35 } 36 return front; 37 } 38 struct node{ 39 int x,y; 40 }a[N],b[N],c[N]; 41 bool cmp(node p,node q){ 42 return p.y<q.y; 43 } 44 int work(node p[],int n1){ 45 sort(p+1,p+1+n1,cmp); 46 int g1=0,n2=0; 47 for(int i=1;i<=n1;i++){ 48 if(i==n1){ 49 p[++n2].y=p[i].y; 50 p[n2].x=g1+p[i].x; 51 break; 52 } 53 if(p[i+1].y==p[i].y){ 54 g1+=p[i].x; 55 } 56 else{ 57 p[++n2].y=p[i].y; 58 p[n2].x=g1+p[i].x; 59 g1=0; 60 } 61 } 62 return n2; 63 } 64 int n,m; 65 int main(){ 66 IO; 67 LinkList L1,L2; 68 L1=(LinkList)malloc(sizeof(LinkNode)); 69 L2=(LinkList)malloc(sizeof(LinkNode)); 70 L1->next=NULL; 71 L2->next=NULL; 72 LinkNode *r1=L1,*r2=L2; 73 cin>>n; 74 for(int i=1;i<=n;i++){ 75 cin>>a[i].x>>a[i].y; 76 } 77 int n1=0,n2=0,n3=0,n4=0,f=0; 78 n1=work(a,n); 79 for(int i=1;i<=n1;i++){ 80 attach(a[i].x,a[i].y,r1); 81 } 82 cin>>m; 83 for(int i=1;i<=m;i++){ 84 cin>>b[i].x>>b[i].y; 85 } 86 n2=work(b,m); 87 for(int i=1;i<=n2;i++){ 88 attach(b[i].x,b[i].y,r2); 89 } 90 LinkList L3=mutiply(L1,L2); 91 L3=L3->next; 92 while(L3){ 93 c[++n3].x=L3->co; 94 c[n3].y=L3->ex; 95 L3=L3->next; 96 } 97 n4=work(c,n3); 98 for(int i=n4;i>1;i--){ 99 if(c[i].x==0)continue; 100 f=1; 101 cout<<c[i].x<<" "<<c[i].y<<" "; 102 } 103 if(c[1].x!=0)cout<<c[1].x<<" "<<c[1].y,f=1; 104 if(!f)cout<<"0 0"; 105 } 106 /* 107 3 108 1 3 2 2 4 3 109 3 110 1 7 2 6 3 5 111 112 2 113 3 2 114 3 2 115 2 116 0 2 117 0 1 118 */